結果

問題 No.922 東北きりきざむたん
ユーザー LayCurseLayCurse
提出日時 2019-11-08 22:22:49
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 47 ms / 2,000 ms
コード長 15,212 bytes
コンパイル時間 3,027 ms
コンパイル使用メモリ 222,232 KB
実行使用メモリ 26,752 KB
最終ジャッジ日時 2024-09-15 01:36:37
合計ジャッジ時間 4,886 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge6
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 3 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 AC 2 ms
5,376 KB
testcase_06 AC 2 ms
5,376 KB
testcase_07 AC 2 ms
5,376 KB
testcase_08 AC 2 ms
5,376 KB
testcase_09 AC 18 ms
12,928 KB
testcase_10 AC 13 ms
6,400 KB
testcase_11 AC 16 ms
10,368 KB
testcase_12 AC 14 ms
19,072 KB
testcase_13 AC 8 ms
7,552 KB
testcase_14 AC 25 ms
20,480 KB
testcase_15 AC 14 ms
20,992 KB
testcase_16 AC 37 ms
14,848 KB
testcase_17 AC 38 ms
14,720 KB
testcase_18 AC 36 ms
14,720 KB
testcase_19 AC 35 ms
14,720 KB
testcase_20 AC 36 ms
14,720 KB
testcase_21 AC 28 ms
12,672 KB
testcase_22 AC 27 ms
12,928 KB
testcase_23 AC 42 ms
15,104 KB
testcase_24 AC 47 ms
15,104 KB
testcase_25 AC 28 ms
15,488 KB
testcase_26 AC 29 ms
15,488 KB
testcase_27 AC 28 ms
15,616 KB
testcase_28 AC 27 ms
26,752 KB
testcase_29 AC 44 ms
18,176 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#pragma GCC optimize ("Ofast")
#include<bits/stdc++.h>
using namespace std;
void *wmem;
char memarr[96000000];
template<class T> inline void walloc1d(T **arr, int x, void **mem = &wmem){
  static int skip[16] = {0, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
  (*mem) = (void*)( ((char*)(*mem)) + skip[((unsigned long long)(*mem)) & 15] );
  (*arr)=(T*)(*mem);
  (*mem)=((*arr)+x);
}
inline void rd(int &x){
  int k;
  int m=0;
  x=0;
  for(;;){
    k = getchar_unlocked();
    if(k=='-'){
      m=1;
      break;
    }
    if('0'<=k&&k<='9'){
      x=k-'0';
      break;
    }
  }
  for(;;){
    k = getchar_unlocked();
    if(k<'0'||k>'9'){
      break;
    }
    x=x*10+k-'0';
  }
  if(m){
    x=-x;
  }
}
inline void wt_L(char a){
  putchar_unlocked(a);
}
inline void wt_L(long long x){
  int s=0;
  int m=0;
  char f[20];
  if(x<0){
    m=1;
    x=-x;
  }
  while(x){
    f[s++]=x%10;
    x/=10;
  }
  if(!s){
    f[s++]=0;
  }
  if(m){
    putchar_unlocked('-');
  }
  while(s--){
    putchar_unlocked(f[s]+'0');
  }
}
template<class S> void arrInsert(const int k, int &sz, S a[], const S aval){
  int i;
  sz++;
  for(i=sz-1;i>k;i--){
    a[i] = a[i-1];
  }
  a[k] = aval;
}
template<class S, class T> void arrInsert(const int k, int &sz, S a[], const S aval, T b[], const T bval){
  int i;
  sz++;
  for(i=sz-1;i>k;i--){
    a[i] = a[i-1];
  }
  for(i=sz-1;i>k;i--){
    b[i] = b[i-1];
  }
  a[k] = aval;
  b[k] = bval;
}
template<class S, class T, class U> void arrInsert(const int k, int &sz, S a[], const S aval, T b[], const T bval, U c[], const U cval){
  int i;
  sz++;
  for(i=sz-1;i>k;i--){
    a[i] = a[i-1];
  }
  for(i=sz-1;i>k;i--){
    b[i] = b[i-1];
  }
  for(i=sz-1;i>k;i--){
    c[i] = c[i-1];
  }
  a[k] = aval;
  b[k] = bval;
  c[k] = cval;
}
struct unionFind{
  int *d;
  int N;
  int M;
  inline void malloc(const int n){
    d = (int*)std::malloc(n*sizeof(int));
    M = n;
  }
  inline void free(void){
    std::free(d);
  }
  inline void walloc(const int n, void **mem=&wmem){
    walloc1d(&d, n, mem);
    M = n;
  }
  inline void init(const int n){
    int i;
    N = n;
    for(i=(0);i<(n);i++){
      d[i] = -1;
    }
  }
  inline void init(void){
    init(M);
  }
  inline int get(int a){
    int t = a;
    int k;
    while(d[t]>=0){
      t=d[t];
    }
    while(d[a]>=0){
      k=d[a];
      d[a]=t;
      a=k;
    }
    return a;
  }
  inline int connect(int a, int b){
    if(d[a]>=0){
      a=get(a);
    }
    if(d[b]>=0){
      b=get(b);
    }
    if(a==b){
      return 0;
    }
    if(d[a] < d[b]){
      d[a] += d[b];
      d[b] = a;
    }
    else{
      d[b] += d[a];
      d[a] = b;
    }
    return 1;
  }
  inline int operator()(int a){
    return get(a);
  }
  inline int operator()(int a, int b){
    return connect(a,b);
  }
  inline int& operator[](const int a){
    return d[a];
  }
  inline int size(int a){
    a = get(a);
    return -d[a];
  }
  inline int sizeList(int res[]){
    int i;
    int sz=0;
    for(i=(0);i<(N);i++){
      if(d[i]<0){
        res[sz++] = -d[i];
      }
    }
    return sz;
  }
}
;
struct graph{
  int N;
  int *es;
  int **edge;
  void setEdgeRootedTree(int N__, int M, int A[], int B[], int root=0, int reorder=0, int cnv[] = NULL, void **mem = &wmem){
    int i;
    int j;
    int k;
    int *dist;
    int *q;
    int qs;
    int qe;
    int *ind;
    void *tmem;
    N = N__;
    tmem = ((char*)(*mem)) + (sizeof(int) * N + 15) + (sizeof(int*) * N + 15) + (sizeof(int) * M + 15 * N);
    walloc1d(&es, N, mem);
    walloc1d(&edge, N, mem);
    for(i=(0);i<(N);i++){
      es[i] = 0;
    }
    for(i=(0);i<(M);i++){
      es[A[i]]++;
      es[B[i]]++;
    }
    for(i=(0);i<(N);i++){
      walloc1d(&edge[i], es[i], &tmem);
    }
    for(i=(0);i<(N);i++){
      es[i] = 0;
    }
    for(i=(0);i<(M);i++){
      edge[A[i]][es[A[i]]++] = B[i];
      edge[B[i]][es[B[i]]++] = A[i];
    }
    walloc1d(&dist, N, &tmem);
    walloc1d(&q, N, &tmem);
    walloc1d(&ind, N, &tmem);
    if(cnv==NULL){
      walloc1d(&cnv, N, &tmem);
    }
    for(i=(0);i<(N);i++){
      dist[i] = -1;
    }
    dist[root] = 0;
    qs = qe = 0;
    q[qe++] = root;
    while(qs < qe){
      i = q[qs++];
      for(j=(0);j<(es[i]);j++){
        k = edge[i][j];
        if(dist[k]==-1){
          dist[k] = dist[i] + 1;
          q[qe++] = k;
        }
      }
    }
    if(reorder == 0){
      for(i=(0);i<(N);i++){
        cnv[i] = i;
      }
      for(i=(0);i<(N);i++){
        ind[i] = i;
      }
    }
    else{
      for(i=(0);i<(N);i++){
        cnv[i] = q[i];
      }
      for(i=(0);i<(N);i++){
        ind[cnv[i]] = i;
      }
    }
    for(i=(0);i<(N);i++){
      es[i] = 0;
    }
    for(i=(0);i<(M);i++){
      j = A[i];
      k = B[i];
      if(dist[j] > dist[k]){
        swap(j, k);
      }
      es[ind[j]]++;
    }
    for(i=(0);i<(N);i++){
      walloc1d(&edge[i], es[i], mem);
    }
    for(i=(0);i<(N);i++){
      es[i] = 0;
    }
    for(i=(0);i<(M);i++){
      j = A[i];
      k = B[i];
      if(dist[j] > dist[k]){
        swap(j, k);
      }
      j = ind[j];
      k = ind[k];
      edge[j][es[j]++] = k;
    }
  }
}
;
struct HLD{
  int N;
  int *es;
  int **edge;
  int *group;
  int *groupind;
  int groupNum;
  int *groupSize;
  int **groupNode;
  int *groupUpNode;
  int *groupDepth;
  void init(graph g, void **mem = &wmem){
    init(g.N, g.es, g.edge, mem);
  }
  void init(int N__, int *es__, int **edge__, void **mem = &wmem){
    int i;
    int j;
    int k;
    int x;
    int y;
    int mx;
    int *q;
    int q_st;
    int q_ed;
    int *sz;
    char *vis;
    void *tmpmem;
    N = N__;
    es = es__;
    edge = edge__;
    walloc1d(&group, N, mem);
    walloc1d(&groupind, N, mem);
    tmpmem = *mem;
    walloc1d(&q, N, &tmpmem);
    walloc1d(&sz, N, &tmpmem);
    walloc1d(&vis, N, &tmpmem);
    for(i=(0);i<(N);i++){
      vis[i] = 0;
    }
    q_st = 0;
    q_ed = 1;
    q[0] = 0;
    vis[0] = 1;
    while(q_st < q_ed){
      i = q[q_st++];
      for(j=(0);j<(es[i]);j++){
        k = edge[i][j];
        if(!vis[k]){
          vis[k] = 1;
          q[q_ed++] = k;
        }
      }
    }
    for(i=(0);i<(N);i++){
      sz[i] = 0;
    }
    for(j=N-1;j>=0;j--){
      i = q[j];
      sz[i] = 1;
      for(k=(0);k<(es[i]);k++){
        sz[i] += sz[edge[i][k]];
      }
    }
    for(i=(0);i<(N);i++){
      group[i] = -1;
    }
    groupNum = 0;
    for(j=(0);j<(N);j++){
      i = q[j];
      if(group[i]>=0){
        continue;
      }
      group[i] = groupNum++;
      groupind[i] = 0;
      for(;;){
        mx = -1;
        for(k=(0);k<(es[i]);k++){
          if(group[edge[i][k]] != -1){
            continue;
          }
          if(mx==-1){
            mx = k;
          }
          else if(sz[edge[i][k]] > sz[edge[i][mx]]){
            mx = k;
          }
        }
        if(mx==-1){
          break;
        }
        group[edge[i][mx]] = group[i];
        groupind[edge[i][mx]] = groupind[i]+1;
        i = edge[i][mx];
      }
    }
    walloc1d(&groupSize, groupNum, mem);
    walloc1d(&groupUpNode, groupNum, mem);
    walloc1d(&groupDepth, groupNum, mem);
    for(i=(0);i<(groupNum);i++){
      groupSize[i] = 0;
    }
    for(i=(0);i<(N);i++){
      groupSize[group[i]]++;
    }
    walloc1d(&groupNode, groupNum, mem);
    for(i=(0);i<(groupNum);i++){
      walloc1d(&groupNode[i], groupSize[i], mem);
    }
    for(i=(0);i<(N);i++){
      groupNode[group[i]][groupind[i]] = i;
    }
    for(i=(0);i<(groupNum);i++){
      groupDepth[i] = -1;
    }
    groupUpNode[0] = -1;
    groupDepth[0] = 0;
    for(x=(0);x<(groupNum);x++){
      for(y=(0);y<(groupSize[x]);y++){
        i = groupNode[x][y];
        for(j=(0);j<(es[i]);j++){
          k = edge[i][j];
          if(x != group[k] && groupDepth[group[k]]==-1){
            groupUpNode[group[k]] = i;
            groupDepth[group[k]] = groupDepth[x] + 1;
          }
        }
      }
    }
  }
  int lca(int x, int y){
    int x1;
    int y1;
    int x2;
    int y2;
    x1 = group[x];
    x2 = groupind[x];
    y1 = group[y];
    y2 = groupind[y];
    while(groupDepth[x1] > groupDepth[y1]){
      x = groupUpNode[x1];
      x1 = group[x];
      x2 = groupind[x];
    }
    while(groupDepth[x1] < groupDepth[y1]){
      y = groupUpNode[y1];
      y1 = group[y];
      y2 = groupind[y];
    }
    while(x1 != y1){
      x = groupUpNode[x1];
      x1 = group[x];
      x2 = groupind[x];
      y = groupUpNode[y1];
      y1 = group[y];
      y2 = groupind[y];
    }
    if(x2 <= y2){
      return x;
    }
    return y;
  }
  int depth(int x){
    int x1;
    int x2;
    int res = 0;
    x1 = group[x];
    x2 = groupind[x];
    while(groupUpNode[x1] != -1){
      res += x2 + 1;
      x = groupUpNode[x1];
      x1 = group[x];
      x2 = groupind[x];
    }
    return res + x2;
  }
  int dist(int x, int y){
    int x1;
    int y1;
    int x2;
    int y2;
    int res = 0;
    x1 = group[x];
    x2 = groupind[x];
    y1 = group[y];
    y2 = groupind[y];
    while(groupDepth[x1] > groupDepth[y1]){
      res += x2 + 1;
      x = groupUpNode[x1];
      x1 = group[x];
      x2 = groupind[x];
    }
    while(groupDepth[x1] < groupDepth[y1]){
      res += y2 + 1;
      y = groupUpNode[y1];
      y1 = group[y];
      y2 = groupind[y];
    }
    while(x1 != y1){
      res += x2 + y2 + 2;
      x = groupUpNode[x1];
      x1 = group[x];
      x2 = groupind[x];
      y = groupUpNode[y1];
      y1 = group[y];
      y2 = groupind[y];
    }
    if(x2 <= y2){
      return res + y2 - x2;
    }
    return res + x2 - y2;
  }
  int up(int x){
    int x1 = group[x];
    int x2 = groupind[x];
    if(x2==0){
      return groupUpNode[x1];
    }
    return groupNode[x1][x2-1];
  }
  int up(int x, int d){
    int x1 = group[x];
    int x2 = groupind[x];
    while(d > x2){
      if(groupUpNode[x1]==-1){
        return -1;
      }
      d -= x2 + 1;
      x = groupUpNode[x1];
      x1 = group[x];
      x2 = groupind[x];
    }
    return groupNode[x1][x2-d];
  }
}
;
int N;
int M;
int Q;
int A[100000];
int B[100000];
int X[100000];
int Y[100000];
int use[100000];
int cnv_g[100000];
int cnv_ind[100000];
int gs;
int gn[100000];
int gm[100000];
int *ga[100000];
int *gb[100000];
int q1s[100000];
int *q1v[100000];
int q2s[100000];
int *q2x[100000];
int *q2y[100000];
int cg;
graph g;
HLD hld;
int arr[100000];
int dp[100000];
void dfs(int n){
  int Lj4PdHRW;
  dp[n] = arr[n];
  for(Lj4PdHRW=(0);Lj4PdHRW<(g.es[n]);Lj4PdHRW++){
    auto &i = g.edge[n][Lj4PdHRW];
    dfs(i);
    dp[n] += dp[i];
  }
}
int main(){
  wmem = memarr;
  int i;
  int j;
  int k;
  int n;
  long long res = 0;
  unionFind uf;
  rd(N);
  rd(M);
  rd(Q);
  {
    int e98WHCEY;
    for(e98WHCEY=(0);e98WHCEY<(M);e98WHCEY++){
      rd(A[e98WHCEY]);A[e98WHCEY] += (-1);
      rd(B[e98WHCEY]);B[e98WHCEY] += (-1);
    }
  }
  {
    int FmcKpFmN;
    for(FmcKpFmN=(0);FmcKpFmN<(Q);FmcKpFmN++){
      rd(X[FmcKpFmN]);X[FmcKpFmN] += (-1);
      rd(Y[FmcKpFmN]);Y[FmcKpFmN] += (-1);
    }
  }
  uf.malloc(N);
  uf.init(N);
  for(i=(0);i<(N);i++){
    uf(A[i], B[i]);
  }
  for(i=(0);i<(N);i++){
    use[uf(i)] = 1;
  }
  for(i=(1);i<(N);i++){
    use[i] += use[i-1];
  }
  gs = use[N-1];
  for(i=(0);i<(N);i++){
    use[i]--;
  }
  for(i=(0);i<(N);i++){
    cnv_g[i] = use[uf(i)];
  }
  for(i=(0);i<(N);i++){
    auto &k = cnv_g[i];
    cnv_ind[i] = gn[k]++;
  }
  for(i=(0);i<(M);i++){
    gm[cnv_g[A[i]]]++;
    gm[cnv_g[B[i]]]++;
  }
  for(i=(0);i<(gs);i++){
    walloc1d(&ga[i], gm[i]);
    walloc1d(&gb[i], gm[i]);
  }
  for(i=(0);i<(gs);i++){
    gm[i] = 0;
  }
  for(i=(0);i<(M);i++){
    k = cnv_g[A[i]];
    arrInsert(gm[k], gm[k], ga[k], cnv_ind[A[i]], gb[k], cnv_ind[B[i]]);
  }
  for(i=(0);i<(Q);i++){
    j = cnv_g[X[i]];
    k = cnv_g[Y[i]];
    if(j==k){
      q2s[j]++;
    }
    if(j!=k){
      q1s[j]++;
      q1s[k]++;
    }
  }
  for(i=(0);i<(gs);i++){
    walloc1d(&q1v[i], q1s[i]);
  }
  for(i=(0);i<(gs);i++){
    walloc1d(&q2x[i], q2s[i]);
  }
  for(i=(0);i<(gs);i++){
    walloc1d(&q2y[i], q2s[i]);
  }
  for(i=(0);i<(gs);i++){
    q1s[i] = q2s[i] = q2s[i] = 0;
  }
  for(i=(0);i<(Q);i++){
    j = cnv_g[X[i]];
    k = cnv_g[Y[i]];
    if(j==k){
      arrInsert(q2s[j], q2s[j], q2x[j], cnv_ind[X[i]], q2y[j], cnv_ind[Y[i]]);
    }
    if(j!=k){
      arrInsert(q1s[j], q1s[j], q1v[j], cnv_ind[X[i]]);
    }
    if(j!=k){
      arrInsert(q1s[k], q1s[k], q1v[k], cnv_ind[Y[i]]);
    }
  }
  for(cg=(0);cg<(gs);cg++){
    g.setEdgeRootedTree(gn[cg], gm[cg], ga[cg], gb[cg]);
    hld.init(g);
    for(i=(0);i<(q2s[cg]);i++){
      res += hld.dist(q2x[cg][i], q2y[cg][i]);
    }
    for(i=(0);i<(gn[cg]);i++){
      arr[i] = 0;
    }
    for(i=(0);i<(q1s[cg]);i++){
      arr[q1v[cg][i]]++;
    }
    dfs(0);
    n = 0;
    for(;;){
      int p1eY1vyF;
      for(p1eY1vyF=(0);p1eY1vyF<(g.es[n]);p1eY1vyF++){
        auto &i = g.edge[n][p1eY1vyF];
        if(2 * dp[i] > dp[0]){
          n = i;
          goto sMcf5Tpe;
        }
      }
      break;
      sMcf5Tpe:;
    }
    for(i=(0);i<(q1s[cg]);i++){
      res += hld.dist(n, q1v[cg][i]);
    }
  }
  wt_L(res);
  wt_L('\n');
  return 0;
}
// cLay varsion 20191108-1

// --- original code ---
// int N, M, Q, A[1d5], B[1d5], X[1d5], Y[1d5];
// 
// int use[1d5], cnv_g[1d5], cnv_ind[1d5];
// int gs, gn[1d5], gm[1d5], *ga[1d5], *gb[1d5];
// int q1s[1d5], *q1v[1d5];
// int q2s[1d5], *q2x[1d5], *q2y[1d5];
// 
// int cg;
// graph g;
// HLD hld;
// int arr[1d5], dp[1d5];
// 
// void dfs(int n){
//   dp[n] = arr[n];
//   rep[g.edge[n]](i,g.es[n]) dfs(i), dp[n] += dp[i];
// }
// 
// {
//   int i, j, k, n;
//   ll res = 0;
//   unionFind uf;
//   rd(N,M,Q,(A--,B--)(M),(X--,Y--)(Q));
// 
//   uf.malloc(N);
//   uf.init(N);
//   rep(i,N) uf(A[i], B[i]);
//   rep(i,N) use[uf(i)] = 1;
//   rep(i,1,N) use[i] += use[i-1];
//   gs = use[N-1];
//   rep(i,N) use[i]--;
//   rep(i,N) cnv_g[i] = use[uf(i)];
//   rep[cnv_g,i](k,N) cnv_ind[i] = gn[k]++;
//   rep(i,M) gm[cnv_g[A[i]]]++, gm[cnv_g[B[i]]]++;
//   rep(i,gs) walloc1d(&ga[i], gm[i]), walloc1d(&gb[i], gm[i]);
//   rep(i,gs) gm[i] = 0;
//   rep(i,M){
//     k = cnv_g[A[i]];
//     arrInsert(gm[k], gm[k], ga[k], cnv_ind[A[i]], gb[k], cnv_ind[B[i]]);
//   }
// 
//   rep(i,Q){
//     j = cnv_g[X[i]];
//     k = cnv_g[Y[i]];
//     if(j==k) q2s[j]++;
//     if(j!=k) q1s[j]++, q1s[k]++;
//   }
//   rep(i,gs) walloc1d(&q1v[i], q1s[i]);
//   rep(i,gs) walloc1d(&q2x[i], q2s[i]);
//   rep(i,gs) walloc1d(&q2y[i], q2s[i]);
//   rep(i,gs) q1s[i] = q2s[i] = q2s[i] = 0;
//   rep(i,Q){
//     j = cnv_g[X[i]];
//     k = cnv_g[Y[i]];
//     if(j==k) arrInsert(q2s[j], q2s[j], q2x[j], cnv_ind[X[i]], q2y[j], cnv_ind[Y[i]]);
//     if(j!=k) arrInsert(q1s[j], q1s[j], q1v[j], cnv_ind[X[i]]);
//     if(j!=k) arrInsert(q1s[k], q1s[k], q1v[k], cnv_ind[Y[i]]);
//   }
// 
//   rep(cg,gs){
//     g.setEdgeRootedTree(gn[cg], gm[cg], ga[cg], gb[cg]);
//     hld.init(g);
//     rep(i,q2s[cg]) res += hld.dist(q2x[cg][i], q2y[cg][i]);
//     rep(i,gn[cg]) arr[i] = 0;
//     rep(i,q1s[cg]) arr[q1v[cg][i]]++;
//     dfs(0);
//     n = 0;
//     for(;;){
//       rep[g.edge[n]](i,g.es[n]) if(2 * dp[i] > dp[0]) n = i, break_continue;
//       break;
//     }
//     rep(i,q1s[cg]) res += hld.dist(n, q1v[cg][i]);
//   }
// 
//   wt(res);
// }
0