NCD 2019

//1170ms 43.9MB
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
#include <stack>
using namespace std;

const int maxn=2e5+100;
const int maxe=1e6+100;
struct edge//邻接表表示图
{
    int to,next;
    int flag;//访问标记
}e[maxe<<1];
int head[maxn],cnt;
stack<int> sta;
int dfn[maxn],low[maxn],belong[maxn],index,n,m,sum,scc;
int fa[maxn];//父结点
int bridge[maxn][2];
void init()//初始化
{
    memset(head,-1,sizeof(head));
    cnt=-1;//边编号
    scc=0;//边双连通分量编号
    index=0;//深度
    sum=0;//桥总数
    memset(low,0,sizeof(low));
    memset(dfn,0,sizeof(dfn));
    memset(fa,0,sizeof(fa));
}
void add_edge(int u,int v)//加边
{
    e[++cnt].to=v;
    e[cnt].flag=0;//标记该无向边是否被访问过，将正向边和反向边一起标记
    e[cnt].next=head[u];
    head[u]=cnt;
}
void tarjan(int u,int f)//dfs确定边双连通分量和桥
{
    dfn[u]=low[u]=++index;
    sta.push(u);
    for(int i=head[u];i!=-1;i=e[i].next)
    {
        int v=e[i].to;
        if(e[i].flag) continue;///只能跳过反向边，不能跳过重边
        ///注意重边,边（u，v）有重边，其不可能是桥，重边相当于两点之间的另一条路，不能合并
        e[i].flag=e[i^1].flag=1;
        if(dfn[v])
            low[u]=min(low[u],dfn[v]);
        else
        {
            tarjan(v,u);
            fa[v]=u;
            low[u]=min(low[u],low[v]);
            if(low[v]>dfn[u])//桥的判断条件
            {
                sum++;
                //存桥，然后根据桥去建新图
                bridge[sum][0]=u;
                bridge[sum][1]=v;
            }
        }
    }
    if(dfn[u]==low[u])//双连通分量
    {
        scc++;
        while(!sta.empty())
        {
            int p=sta.top();sta.pop();
            belong[p]=scc;
            if(p==u) break;
        }
    }
}
int node,d[maxn],ans;
void dfs(int u,int dist)//dfs确定每个结点距初始结点的距离
{
    d[u]=dist;
    if(d[u]>ans) ans=d[u],node=u;
    for(int i=head[u];i!=-1;i=e[i].next)
    {
        int v=e[i].to;
        if(d[v]!=-1) continue;
        dfs(v,dist+1);
    }
}
int main()
{
    int T;
    scanf("%d", &T);
    while(T--)
    {
        scanf("%d%d",&n,&m);
        if(n==0 && m==0) break;
        init();
        while(m--)//建图
        {
            int u,v;
            scanf("%d%d",&u,&v);
            add_edge(u,v);
            add_edge(v,u);
        }
        for(int i=1;i<=n;i++)//初始图不一定连通
            if(!dfn[i]) tarjan(i,0);//tarjan算法求所有双连通分量和桥

        //根据桥建新图
        memset(head,-1,sizeof(head));
        cnt=-1;
        for(int i=1;i<=sum;i++)
        {
            int u=belong[bridge[i][0]];
            int v=belong[bridge[i][1]];
            add_edge(u,v);
            add_edge(v,u);
        }
        //两遍dfs求树直径
        ans=0;
        memset(d,-1,sizeof(d));
        dfs(1,0);//从根到最远点node
        memset(d,-1,sizeof(d));
        ans=0;
        dfs(node,0);//从最远点到另一个最远点
        printf("%d\n",sum-ans);
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1010;
const int mod = 1e9 + 7;
int T, N;
int A[maxn], dp[maxn], c[maxn];

int main() {
    scanf("%d", &T);
    while(T --) {
        scanf("%d", &N);
        for(int i = 0; i < N; i ++)
            scanf("%d", &A[i]), dp[i] = 1, c[i] = 1;

        for(int i = 0; i < N; i ++) {
            for(int j = 0; j < i; j ++) {
                if(A[i] <= A[j]) continue;
                if(dp[j] + 1 == dp[i]) {
                  c[i] = (c[i] + c[j]) % mod;
                } else if(dp[j] + 1 > dp[i]) {
                    dp[i] = dp[j] + 1;
                    c[i] = c[j];
                }
            }
        }

        int ans1 = -1, ans2;
        for(int i = 0; i < N; i ++) {
            if(dp[i] > ans1) {
                ans1 = dp[i];
                ans2 = c[i];
            } else if(dp[i] == ans1) {
                ans2 = (ans2 + c[i]) % mod;
            }
        }

        printf("%d %d\n", ans1, ans2);

    }
    return 0;
}
close

#include <bits/stdc++.h>
using namespace std;

int main() {
  int T;
  scanf("%d", &T);
  while(T--) {
    int x, y;
    scanf("%d%d", &x, &y);
    if(x == y) {
        printf("Iskandar\n");
    } else if(x > y) {
      printf("Bashar\n");
    } else {
      printf("Hamada\n");
    }
  }
  return 0;
}

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e5 + 10;

const long long mod = 1e9 + 7;

long long base[2] = {131LL, 313LL};

long long b[2][maxn];

char str[2][maxn];

int T, n, m;

long long s[2][2][4 * maxn];

void pushUp(int t, int rt) {
  for(int i = 0; i < 2; i ++) {
    s[t][i][rt] = (s[t][i][2 * rt] + s[t][i][2 * rt + 1]) % mod;
  }
}

void update(int t, int pos, long long dealta, int l, int r, int rt) {
  if(l == r) {
    for(int i = 0; i < 2; i ++) {
      s[t][i][rt] = (s[t][i][rt] + (b[i][pos] * dealta % mod)) % mod;
    }
    return;
  }

  int mid = (l + r) / 2;
  if(pos <= mid) update(t, pos, dealta, l, mid, 2 * rt);
  else update(t, pos, dealta, mid + 1, r, 2 * rt + 1);

  pushUp(t, rt);
}

pair<long long, long long> sum(int t, int L, int R, int l, int r, int rt) {
  if(L <= l && r <= R) {
    return make_pair(s[t][0][rt], s[t][1][rt]);
  }

  int mid = (l + r) / 2;

  pair<long long, long long> left = make_pair(0LL, 0LL);
  pair<long long, long long> right = make_pair(0LL, 0LL);

  if(L <= mid) left = sum(t, L, R, l, mid, 2 * rt);
  if(R > mid) right = sum(t, L, R, mid + 1, r, 2 * rt + 1);

  return make_pair((left.first + right.first) % mod, (left.second + right.second) % mod);
}

void op1(int pos, char sign) {

  int pos0 = pos;
  int pos1 = n - pos + 1;

  if(str[0][pos0] == sign) {
    return;
  }

  long long delta = (sign - str[0][pos0] + mod) % mod;

  update(0, pos0, delta, 1, n, 1);
  update(1, pos1, delta, 1, n, 1);

  str[0][pos0] = sign;
  str[1][pos1] = sign;
}

void op2(int L, int R) {

  int L0 = L, R0 = R;
  int L1 = n - R + 1, R1 = n - L + 1;

  pair<long long, long long> pi0 = sum(0, L0, R0, 1, n, 1);
  pair<long long, long long> pi1 = sum(1, L1, R1, 1, n, 1);

  if(L0 <= L1) {
    pi0.first = pi0.first * b[0][L1 - L0] % mod;
    pi0.second = pi0.second * b[1][L1 - L0] % mod;
  }
  else {
    pi1.first = pi1.first * b[0][L0 - L1] % mod;
    pi1.second = pi1.second * b[1][L0 - L1] % mod;
  }

  if(pi0 == pi1) {
    printf("Adnan Wins\n");
  } else {
    printf("ARCNCD!\n");
  }
}

int main() {

  b[0][0] = 1LL;
  b[1][0] = 1LL;

  for(int i = 1; i < maxn; i ++) {
    b[0][i] = b[0][i - 1] * base[0] % mod;
    b[1][i] = b[1][i - 1] * base[1] % mod;
  }

  scanf("%d", &T);

  while(T --) {
    scanf("%d%d", &n, &m);

    memset(s, 0, sizeof s);

    scanf("%s", str[0] + 1);
    for(int i = 1; i <= n; i ++) {
      str[1][i] = str[0][n - i + 1];
    }

/*
    for(int i = 1; i <= n; i ++) {
      printf("%c", str[0][i]);
    }
printf("\n");
    for(int i = 1; i <= n; i ++) {
      printf("%c", str[1][i]);
    }
*/

    for(int t = 0; t < 2; t ++) {
        for(int i = 1; i <= n; i ++) {
            update(t, i, (long long)(str[t][i] - ‘a‘ + 1), 1, n, 1);
        }
    }

    while(m --) {
      int tp;
      scanf("%d", &tp);
      if(tp == 1) {
        int pos;
        char sign[5];
        scanf("%d%s", &pos, sign);
        op1(pos, sign[0]);
      } else {
        int L, R;
        scanf("%d%d", &L, &R);
        op2(L, R);
      }

    }

  }

  return 0;
}

#include <bits/stdc++.h>
using namespace std;

int main() {
  int T;
  scanf("%d", &T);
  while(T--) {
    long long n, k;
    scanf("%lld%lld", &n, &k);
    n = n - k;
    if(n == 0) {
      printf("0\n");
      continue;
    }

    long long ans = n / 6LL;
    if(n % 6LL != 0) ans ++;

    printf("%lld\n", ans);
  }
  return 0;
}

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e5 + 10;
int T, N, M, Q;
int f[maxn];

void init() {
    for(int i = 1; i <= N; i ++)
        f[i] = i;
}

int Find(int x) {
    if(f[x] != x) f[x] = Find(f[x]);
    return f[x];
}

void Merge(int x, int y) {
    int fx = Find(x);
    int fy = Find(y);
    if(fx != fy) {
        f[fx] = fy;
    }
}

int main() {
    scanf("%d", &T);
    while(T --) {
        string ans = "";
        scanf("%d%d%d", &N, &M, &Q);
        init();
        while(M --) {
            int st, en;
            scanf("%d%d", &st, &en);
            Merge(st, en);
        }
        while(Q --) {
            int qx, qy;
            scanf("%d%d", &qx, &qy);
            if(Find(qx) == Find(qy)) ans += ‘1‘;
            else ans += ‘0‘;
        }
        cout << ans << endl;
    }
    return 0;
}

#include <bits/stdc++.h>

const int maxn = 2e5 + 10;

int T, n, m;
int c[maxn], x[maxn];

int f(int a, int b) {
  b = b % n;
  b = (b + n) % n;
  a --;
  a = (a + b) % n;
  a ++;
  return a;
}

void add(int L, int R) {
//printf("[%d, %d]\n", L, R);

  c[L] ++;
  c[R + 1] --;
}

int main() {
  scanf("%d", &T);
  while(T --) {

    memset(c, 0, sizeof c);

    scanf("%d%d", &n, &m);
    for(int i = 1; i <= m; i ++) {
      scanf("%d", &x[i]);
    }

    for(int i = 1; i <= m; i ++) {
      int y;
      scanf("%d", &y);

      if(y == 0) add(x[i], x[i]);
      else if(abs(y) == n) { add(1, n); add(x[i], x[i]); }
      else if(abs(y) == n - 1) { add(1, n); }
      else {
        int e = f(x[i], y);

        if(y > 0) {
            if(e >= x[i]) add(x[i], e);
            else { add(x[i], n); add(1, e); }
        }
        else {
            if(e <= x[i]) add(e, x[i]);
            else { add(1, x[i]); add(e, n); }
        }
      }
    }

    for(int i = 1; i <= n + 1; i ++) {
      c[i] = c[i] + c[i - 1];
    }

    int ans1 = 0, ans2 = 0;
    for(int i = 1; i <= n; i ++) {
        if(c[i] > ans1) {
            ans1 = c[i];
            ans2 = i;
        }
    }

    printf("%d %d\n", ans2, ans1);
  }
  return 0;
}

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e5 + 10;
int T, N;
long long X;
long long a[maxn], sum[maxn];

bool check(int st, int en) {
    long long ans = sum[en] - sum[st - 1];
    if(ans < X) return true;
    return false;
}

int main() {
    scanf("%d", &T);
    while(T --) {
        scanf("%d%lld", &N, &X);
        memset(sum, 0, sizeof(sum));
        for(int i = 1; i <= N; i ++) {
            scanf("%lld", &a[i]);
            if(i == 1) sum[i] = a[i];
            else sum[i]  =sum[i - 1] + a[i];
        }

        long long ans = 0;
        for(int i = 1; i <= N; i ++) {
            int l = i, r = N, mid, p = 0;
            while(l <= r) {
                mid = (l + r) / 2;
                if(check(i, mid)) {
                    l = mid + 1;
                    p = mid;
                } else r = mid - 1;
            }
            ans = ans + max(0, (p - i + 1));
        }
        printf("%lld\n", ans);
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

int main() {
  int T;
  scanf("%d", &T);
  while(T--) {
    int n;
    scanf("%d", &n);
    for(int i = 1; i <= n; i ++) {
      int x;
      scanf("%d", &x);
      int ans = 0;
      while(x > 0) {
        ans = ans + x % 2;
        x = x / 2;
      }
      printf("%d", ans);
      if(i < n) printf(" ");
      else printf("\n");
    }
  }
  return 0;
}

#include <bits/stdc++.h>
using namespace std;

int T;
int B1, P1, B2, P2;

int main() {
    scanf("%d", &T);
    while(T --) {
        scanf("%d%d%d%d", &B1, &P1, &B2, &P2);

        if(B1 == 0 || B2 == 0) {
          if(B1 == B2) printf("Lazy\n");
          else if(B1 > B2) printf("HaHa\n");
          else printf("Congrats\n");
          continue;
        }

        double num1 = 1.0 * P1 * log(1.0 * B1);
        double num2 = 1.0 * P2 * log(1.0 * B2);

        if(fabs(num1 - num2) <= 1e-7) printf("Lazy\n");
        else if(num1 > num2) printf("HaHa\n");
        else printf("Congrats\n");
    }
    return 0;
}