CodeChef September 2014 Cook-Off 5問目 - Updating Edges on Trees

Source

CodeChef September 2014 Cook-Off
問題文

問題概要

ノード数 $N$ の木が与えられる.
$M_1$ 個のクエリと,$M_2$ 個のクエリに答える問題.
最初に $M_1$ 個のクエリを行い,その後,$M_2$ 個のクエリを行う問題.
各辺には重みがあり,最初は重みはすべて $0$.
最初の $M_1$ 個のそれぞれのクエリでは,ノード $A,B,C,D$ が与えられるので,ノード $A,B$ 間のパスに含まれる枝のうち,ノード $C,D$ 間のパスに含まれない枝の重みを全て $+1$ する.
その後の $M_2$ 個のそれぞれのクエリでは,ノード $E,F$ が与えられるので,ノード $E,F$ 間のパスに含まれる枝の重みの和を求める.

解法

適当な根を設定して,根付き木で考える.
ダブリングなどを用いて,LCAを計算できるようにしておき,各ノードの根からの距離も求めておく.
まず最初の $M_1$ 個のクエリを考える.
$x$ を ${\rm LCA}(A,B)$ として,パス $(A,x)$ に含まれる枝の重みを $+1$ し,$(B,x)$ に含まれる枝の重みを $+1$ する.
その中で,$(C,D)$ に含まれるものは,改めて $-1$ する.
それは,$(A,x)$ にも $(C,D)$ にも含まれる枝などを求めれば良い.
$(A,x)$ に含まれるところまで移動するために,$C$ を ${\rm LCA}(C,A)$ に置き換え,$D$ を ${\rm LCA}(D,A)$ に置き換える.
また,$C$ の根からの距離が $x$ より近い場合は,$C$ を $x$ に置き換え,$D$ に関しても同様.
すると,パス $(C,D)$ は $(A,x)$ 上になるので,その部分に含まれる枝の重みを $-1$ する.
枝の重みの変化をどのように処理するかというと,変化する部分の値のみを計算しておいて,後で累積和を求めることによって,各枝の重みを計算する.
つまり,$(A,x)$ に含まれる枝に $+1$ する場合は,$x$ に $-1$ し,$A$ に $+1$ しておく(ノード $x$ はノード $x$ から親に移動する枝の重みを保持しているとする).
$M_1$ 個のクエリが終わった時に,根からDFSして,自分を根とする部分木に含まれる値の和を求めれば良い.
また,更に累積和を取り,ある部分の和を求めれるようにしておけば,後の $M_2$ のクエリに答えることもできる.

C++によるスパゲッティなソースコード

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

#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define mygc(c) (c)=getchar_unlocked()
#define mypc(c) putchar_unlocked(c)

#define ll long long
#define ull unsigned ll

void reader(int *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}
void reader(int *x, int *y){reader(x);reader(y);}
void reader(int *x, int *y, int *z){reader(x);reader(y);reader(z);}
void reader(ll *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}
int reader(char c[]){int i,s=0;for(;;){mygc(i);if(i!=' '&&i!='\n'&&i!='\r'&&i!='\t'&&i!=EOF) break;}c[s++]=i;for(;;){mygc(i);if(i==' '||i=='\n'||i=='\r'||i=='\t'||i==EOF) break;c[s++]=i;}return s;}

void writer(int x, char c){int s=0,m=0;char f[10];if(x<0)m=1,x=-x;while(x)f[s++]=x%10,x/=10;if(!s)f[s++]=0;if(m)mypc('-');while(s--)mypc(f[s]+'0');mypc(c);}
void writer(ll x, char c){int s=0,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)mypc('-');while(s--)mypc(f[s]+'0');mypc(c);}
void writer(const char c[]){int i;for(i=0;c[i]!='\0';i++)mypc(c[i]);}

void* setUndirectEdge(int N, int M, int A[], int B[], int **es, int ***edge, void *workMemory){
  int i;
  
  *es = (int*)workMemory;
  *edge = (int**)((*es)+N);
  (*edge)[0] = (int*)((*edge)+N);

  rep(i,N) (*es)[i] = 0;
  rep(i,M) (*es)[A[i]]++, (*es)[B[i]]++;

  REP(i,1,N) (*edge)[i] = (*edge)[i-1] + (*es)[i-1];
  workMemory = (void*)((*edge)[N-1] + (*es)[N-1]);

  rep(i,N) (*es)[i] = 0;
  rep(i,M) (*edge)[A[i]][(*es)[A[i]]++]=B[i], (*edge)[B[i]][(*es)[B[i]]++]=A[i];

  return workMemory;
}


void getDepthOfTreeDFS(int node, int bef, int *depth, int *es, int **edge){
  int i, k;
  rep(i,es[node]){
    k=edge[node][i];
    if(bef==k) continue;
    depth[k] = depth[node] + 1;
    getDepthOfTreeDFS(k, node, depth, es, edge);
  }
}

void* getDepthOfTree(int N, int root, int *es, int **edge, int **depth, void *workMemory){
  *depth = (int*)workMemory;
  workMemory = (void*)((*depth)+N);
  (*depth)[root] = 0;
  getDepthOfTreeDFS(root, -1, *depth, es, edge);
  return workMemory;
}

template<class T>
void doublingRMQBuild(T arr[], int n, int res[]){
  int i, k, hf;

  rep(i,n) res[i] = i;
  for(k=1;;k++){
    hf = (1<<(k-1)); if(hf >= n) break;
    rep(i,n){
      res[n*k+i] = res[n*(k-1)+i];
      if(i+hf < n && arr[res[n*k+i]] > arr[res[n*(k-1)+i+hf]]) res[n*k+i] = res[n*(k-1)+i+hf];
    }
  }
}

template<class T>
void* doublingRMQBuild(T arr[], int n, int **res, void *workMemory){
  int i, k, hf;

  *res = (int*)workMemory;
  rep(i,n) (*res)[i] = i;
  for(k=1;;k++){
    hf = (1<<(k-1)); if(hf >= n) break;
    rep(i,n){
      (*res)[n*k+i] = (*res)[n*(k-1)+i];
      if(i+hf < n && arr[(*res)[n*k+i]] > arr[(*res)[n*(k-1)+i+hf]]) (*res)[n*k+i] = (*res)[n*(k-1)+i+hf];
    }
  }

  return (void*)((*res)+n*k);
}

template<class T>
int doublingRMQQuery(T arr[], int n, int rmq[], int a, int b){
  int dep, wid = b-a+1, A, B;
  for(dep=0;(1<<(dep+1))<=wid;dep++);
  A = rmq[n*dep+a];
  B = rmq[n*dep+b-(1<<dep)+1];
  if(arr[A] > arr[B]) A = B;
  return A;
}

struct LCA{
  int *depth, *vs, *id, *rmq;
  int N, *es, **edge;

  void dfs(int node, int bef, int dep, int *num){
    int i, k;
    id[node] = *num;
    vs[*num] = node;
    depth[(*num)++] = dep;
    rep(i,es[node]){
      k = edge[node][i];
      if(k==bef) continue;
      dfs(k, node, dep+1, num);
      vs[*num] = node;
      depth[(*num)++] = dep;
    }
  }
  
  void* init(int N_, int root, int *es_, int **edge_, void *workMemory){
    int num = 0;
    N = N_;
    es = es_;
    edge = edge_;
    depth = (int*)workMemory;
    vs = depth+2*N-1;
    id = vs+2*N-1;
    dfs(root, -1, 0, &num);
    workMemory = doublingRMQBuild(depth, 2*N-1, &rmq, (void*)(id+N));
    return workMemory;
  }
  
  int get(int a, int b){
    int k = doublingRMQQuery(depth, 2*N-1, rmq, min(id[a],id[b]), max(id[a],id[b]));
    return vs[k];
  }
  
  int getDepth(int a, int b){
    int k = doublingRMQQuery(depth, 2*N-1, rmq, min(id[a],id[b]), max(id[a],id[b]));
    return depth[k];
  }
};

int N, M1, M2;
int A[111111], B[111111];
int **edge, *es;
int depth[110000];

int up[110000];
ll vald[110000], val[110000];
ll sum[110000];

void dfs(int node, int bef){
  int i, j, k;
  val[node] = vald[node];
  rep(i,es[node]){
    k=edge[node][i];
    if(k==bef) continue;
    dfs(k, node);
    val[node] += val[k];
  }
}

void dfs2(int node, int bef){
  int i, j, k;
  sum[node] = val[node];
  if(up[node]>=0) sum[node] += sum[up[node]];
  rep(i,es[node]){
    k=edge[node][i];
    if(k==bef) continue;
    dfs2(k, node);
  }
}

int main(){
  int i, j, k;
  int a, b, c, d, x, cx, dx, z;
  ll res;
  LCA lca;
  void *mem = malloc(100000000);

  reader(&N,&M1,&M2);
  rep(i,N-1){
    reader(A+i,B+i);
    A[i]--; B[i]--;
  }
  mem = setUndirectEdge(N, N-1, A, B, &es, &edge, mem);
  getDepthOfTreeDFS(0, -1, depth, es, edge);
  mem = lca.init(N, 0, es, edge, mem);

  rep(i,N) up[i] = -1;
  rep(i,N) rep(j,es[i]){
    k = edge[i][j];
    if(depth[k]==depth[i]-1) up[i] = k;
  }

  rep(i,N) vald[i] = val[i] = 0;
  while(M1--){
    reader(&a,&b); a--; b--;
    reader(&c,&d); c--; d--;

    x = lca.get(a, b);
    vald[a]++; vald[b]++;
    vald[x]-=2;

    cx = lca.get(a, c); if(depth[cx] < depth[x]) cx = x;
    dx = lca.get(a, d); if(depth[dx] < depth[x]) dx = x;
    z = lca.get(cx, dx);
    vald[cx]--; vald[dx]--;
    vald[z]+=2;

    cx = lca.get(b, c); if(depth[cx] < depth[x]) cx = x;
    dx = lca.get(b, d); if(depth[dx] < depth[x]) dx = x;
    z = lca.get(cx, dx);
    vald[cx]--; vald[dx]--;
    vald[z]+=2;
  }
  dfs(0,-1);
  dfs2(0,-1);

//  rep(i,N) printf("vald %d %lld\n",i,vald[i]);
//  rep(i,N) printf("val  %d %lld\n",i,val[i]);
//  rep(i,N) printf("sum  %d %lld\n",i,sum[i]);

  while(M2--){
    reader(&a,&b); a--; b--;
    x = lca.get(a, b);
    res = sum[a] + sum[b];
    res -= 2*sum[x];
    writer(res,'\n');
  }

  return 0;
}

Current time: 2017年11月22日00時47分55秒
Last modified: 2014年09月22日21時48分34秒 (by laycrs)
Tags: Competitive_Programming CodeChef CodeChef_CookOff CookOff_201409
トップページに戻る

Logged in as: unknown user (not login)

ログイン: