2015年06月30日13時01分26秒に更新されたバージョンを表示しています．
最新のページはこちらをご覧ください．

AtCoder Regular Contest #039 D問題 - 旅行会社高橋君

Source

AtCoder Regular Contest #039
問題文

問題概要

ノード数 $N$，枝数 $M$ の連結な単純無向グラフが与えられる．
$Q$ 個のクエリに答える問題．
各クエリでは，頂点番号 $A,B,C$ が与えられるので，ノード $A$ から $B$ を経由してノード $C$ に移動する経路のうち，同じ枝を $2$ 回以上通らないものが存在するかどうかを求める．

解法

ノードに対する二重連結成分の中は自由に行って戻ることができるから，$A$ から $B$ に移動して，$B$ から $C$ に移動する際に同じ橋を通らなければ良い．
これは，つまり，二重連結成分分解して，木にした後，$A$ から $B$ に移動して，$B$ から $C$ に移動する場合と，$A$ から直接 $C$ に移動するときに通る枝（もとのグラフの橋）の数が等しければ良い．
よって，二重連結成分分解して得られる木に対して，ノード間の距離をたくさん答える問題になる．
これは，適当に根付き木にしておて，各ノードの深さを計算しておいて，ダブリング等でLCAを計算できるようにしておけば良い．
時間計算量はLCAの計算方法にも寄るが $O(N \log N + M + Q \log N)$ 程度．

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)

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);}
template <class T, class S> void reader(T *x, S *y){reader(x);reader(y);}
template <class T, class S, class U> void reader(T *x, S *y, U *z){reader(x);reader(y);reader(z);}

void writer(const char x[], char c){int i;for(i=0;x[i]!='\0';i++)mypc(x[i]);mypc(c);}
template<class T> void writerLn(T x){writer(x,'\n');}

void* readUndirectedGraph(int N, int M, int **es, int ***edge, void *mem, int origin=0){int i,*A;A=((int*)(((int**)mem)+N)+N+2*M);rep(i,2*M)reader(A+i),A[i]-=origin;*es=(int*)mem;*edge=(int**)((*es)+N);memset(*es,0,sizeof(int)*N);rep(i,2*M)(*es)[A[i]]++;(*edge)[0]=(int*)((*edge)+N);REP(i,1,N)(*edge)[i]=(*edge)[i-1]+(*es)[i-1];memset(*es,0,sizeof(int)*N);for(i=0;i<2*M;i+=2)(*edge)[A[i]][(*es)[A[i]]++]=A[i+1],(*edge)[A[i+1]][(*es)[A[i+1]]++]=A[i];return A;}
inline void biconnectedComponentsDFS(int *es, int **edge, int v, int u, int *res, int *rt, int &rts, int *S, int &Ss, int *inS, int *num, int &tm){int i,k,w;num[v]=++tm;S[Ss++]=v;inS[v]=1;rt[rts++]=v;rep(i,es[v]){w=edge[v][i];if(!num[w])biconnectedComponentsDFS(es,edge,w,v,res,rt,rts,S,Ss,inS,num,tm);else if(u!=w&&inS[w])while(num[rt[rts-1]]>num[w])rts--;}if(v==rt[rts-1]){k=S[Ss-1];for(;;){w=S[--Ss];inS[w]=0;res[w]=k;if(v==w)break;}rts--;}}
int biconnectedComponents(int N, int *es, int **edge, int res[], void *mem){int i,k,*r,*S,*m,*F,Z=0,s=0,t=0;pair<int,int>*a;m=(int*)mem;r=m+N;S=r+N;F=S+N;memset(m,0,sizeof(int)*N);memset(F,0,sizeof(int)*N);rep(i,N)if(!m[i])biconnectedComponentsDFS(es,edge,i,N,res,r,Z,S,s,F,m,t);a=(pair<int,int>*)mem;rep(i,N)a[i].first=res[i],a[i].second=i;sort(a,a+N);k=0;rep(i,N){if(i&&a[i].first!=a[i-1].first)k++;res[a[i].second]=k;}return k+1;}
void* getReducedTree(int N, int *es, int **edge, int ind[], int tn, int **tes, int ***tedge, void *mem){int i,j,k,M=0,*A;rep(i,N)M+=es[i];A=((int*)(((int**)mem)+tn)+tn+M);*tes=(int*)mem;*tedge=(int**)((*tes)+tn);memset(*tes,0,sizeof(int)*tn);M=0;rep(i,N)rep(j,es[i]){k=edge[i][j];if(ind[i]<ind[k]){A[2*M]=ind[i];A[2*M+1]=ind[k];(*tes)[ind[i]]++;(*tes)[ind[k]]++;M++;}}(*tedge)[0]=(int*)((*tedge)+tn);REP(i,1,tn)(*tedge)[i]=(*tedge)[i-1]+(*tes)[i-1];memset(*tes,0,sizeof(int)*tn);for(i=0;i<2*M;i+=2)(*tedge)[A[i]][(*tes)[A[i]]++]=A[i+1],(*tedge)[A[i+1]][(*tes)[A[i+1]]++]=A[i];return(*tedge)[tn-1]+(*tes)[tn-1];}

template<class T> void doublingRMQBuild(T arr[], int n, int res[]){int i,k,h;rep(i,n)res[i]=i;for(k=1;;k++){h=(1<<(k-1));if(h>=n)break;rep(i,n){res[n*k+i]=res[n*(k-1)+i];if(i+h<n&&arr[res[n*k+i]]>arr[res[n*(k-1)+i+h]])res[n*k+i]=res[n*(k-1)+i+h];}}}
template<class T> void* doublingRMQBuild(T arr[], int n, int **res, void *workMemory){int i,k,h;*res=(int*)workMemory;rep(i,n)(*res)[i]=i;for(k=1;;k++){h=(1<<(k-1));if(h>=n)break;rep(i,n){(*res)[n*k+i]=(*res)[n*(k-1)+i];if(i+h<n&&arr[(*res)[n*k+i]]>arr[(*res)[n*(k-1)+i+h]])(*res)[n*k+i]=(*res)[n*(k-1)+i+h];}}return (void*)((*res)+n*k);}
template<class T> int doublingRMQQuery(T arr[], int n, int rmq[], int a, int b){int d,w=b-a+1,A,B;for(d=0;(1<<(d+1))<=w;d++);A=rmq[n*d+a];B=rmq[n*d+b-(1<<d)+1];return arr[A]>arr[B]?B:A;}
struct LCA{
  int *depth, *vs, *id, *rmq, 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 m=0;N=N_;es=es_;edge=edge_;depth=(int*)workMemory;vs=depth+2*N-1;id=vs+2*N-1;dfs(root,-1,0,&m);return doublingRMQBuild(depth,2*N-1,&rmq,(void*)(id+N));}
  int get(int a, int b){return vs[doublingRMQQuery(depth,2*N-1,rmq,min(id[a],id[b]),max(id[a],id[b]))];}
  int getDepth(int a, int b){return depth[doublingRMQQuery(depth,2*N-1,rmq,min(id[a],id[b]),max(id[a],id[b]))];}
  int dist(int a, int b){return depth[id[a]]+depth[id[b]]-getDepth(a,b)*2;}
};

char memarr[147000000]; void *mem = memarr;

int N, M, Q;
int A, B, C;

int *es, **edge, *tes, **tedge;
int cone[110000];
int node;

int main(){
  int i, j, k, dist1, dist2;
  LCA lca;

  reader(&N,&M);
  mem = readUndirectedGraph(N, M, &es, &edge, mem, 1);
  node = biconnectedComponents(N, es, edge, cone, mem);
  mem = getReducedTree(N, es, edge, cone, node, &tes, &tedge, mem);

  mem = lca.init(node, 0, tes, tedge, mem);

  reader(&Q);
  rep(i,Q){
    reader(&A,&B,&C);
    A = cone[A-1];
    B = cone[B-1];
    C = cone[C-1];

    dist1 = lca.dist(A,B) + lca.dist(B,C);
    dist2 = lca.dist(A,C);

    writerLn(dist1==dist2?"OK":"NG");
  }

  return 0;
}

Current time: 2024年04月18日18時43分35秒
Last modified: 2015年06月30日13時01分26秒 (by laycrs)
Tags: Competitive_Programming AtCoder AtCoder_Regular_Contest ARC039 ARC_D
トップページに戻る

Logged in as: unknown user (not login)

ログイン：