제출 #60793

#제출 시각아이디문제언어결과실행 시간메모리
60793Vahan열대 식물원 (Tropical Garden) (IOI11_garden)C++17
100 / 100
2871 ms46232 KiB
#include "garden.h" #include "gardenlib.h" #include<vector> #include<iostream> using namespace std; int p,u[400000],u1[400000],u2[400000],l1[400000],l2[400000]; int a[400000]; const int MAXN=400000; vector<int> g[400005],inv[400000]; int dfs1(int v) { if(v==2*p) return 1; if(u[v]==1) return -MAXN; u[v]=1; return dfs1(a[v])+1; } int dfs2(int v) { if(v==2*p+1) return 1; if(u[v]==1) return -MAXN; u[v]=1; return dfs2(a[v])+1; } void dfs11(int v,int h) { if(u1[v]==1) return; u1[v]=1; l1[v]=h; for(int i=0;i<inv[v].size();i++) { int to=inv[v][i]; dfs11(to,h+1); } } void dfs22(int v,int h) { if(u2[v]==1) return; u2[v]=1; l2[v]=h; for(int i=0;i<inv[v].size();i++) { int to=inv[v][i]; dfs22(to,h+1); } } void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) { p=P; for(int i=0;i<M;i++) { g[R[i][0]].push_back(R[i][1]); g[R[i][1]].push_back(R[i][0]); } for(int i=0;i<N;i++) { if(g[i].size()==1) { if(g[g[i][0]][0]==i) a[2*i+1]=2*g[i][0]+1; else a[2*i+1]=2*g[i][0]; a[2*i]=a[2*i+1]; } else { if(g[g[i][0]][0]==i) a[2*i]=2*g[i][0]+1; else a[2*i]=2*g[i][0]; if(g[g[i][1]][0]==i) a[2*i+1]=2*g[i][1]+1; else a[2*i+1]=2*g[i][1]; } } for(int i=0;i<2*N;i++) { inv[a[i]].push_back(i); l1[i]=-1; l2[i]=-1; } int r1=dfs1(a[2*P]); if(r1<0) r1=0; for(int i=0;i<2*N;i++) u[i]=0; int r2=dfs2(a[2*P+1]); if(r2<0) r2=0; dfs11(2*p,0); dfs22(2*p+1,0); for(int i=0;i<Q;i++) { int an=0; for(int j=0;j<N;j++) { if(r1==0 && G[i]==l1[2*j]) an++; else if(r1>0 && G[i]-l1[2*j]>=0 && (G[i]-l1[2*j])%r1==0 && l1[2*j]!=-1) an++; else if(r2==0 && G[i]==l2[2*j]) an++; else if(r2>0 && G[i]-l2[2*j]>=0 && (G[i]-l2[2*j])%r2==0 && l2[2*j]!=-1) an++; } answer(an); } }

컴파일 시 표준 에러 (stderr) 메시지

garden.cpp: In function 'void dfs11(int, int)':
garden.cpp:34:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<inv[v].size();i++)
                 ~^~~~~~~~~~~~~~
garden.cpp: In function 'void dfs22(int, int)':
garden.cpp:46:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<inv[v].size();i++)
                 ~^~~~~~~~~~~~~~
garden.cpp: In function 'void count_routes(int, int, int, int (*)[2], int, int*)':
garden.cpp:66:13: warning: this 'else' clause does not guard... [-Wmisleading-indentation]
             else
             ^~~~
garden.cpp:68:17: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'else'
                 a[2*i]=a[2*i+1];
                 ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...