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: 2017年09月22日22時31分53秒
Last modified: 2015年07月04日08時09分29秒 (by laycrs)
Tags: Competitive_Programming AtCoder AtCoder_Regular_Contest ARC039 ARC_D
トップページに戻る

Logged in as: unknown user (not login)

ログイン: