# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
88005 | Pajaraja | Tropical Garden (IOI11_garden) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
vector<int> h[150007],g[300007];
int d[2][300007],nxt[300007];
void dfs(int s,int k,int di)
{
if(d[k][s]!=-1)
{
d[k][s]=di;
return;
}
d[k][s]=di;
for(int i=0;i<g[s].size();i++) dfs(g[s][i],k,di+1);
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
int n=N;
for(int i=0;i<M;i++)
{
int p;
p=R[i][1];
h[R[i][0]].push_back(p);
p=R[i][0];
h[R[i][1]].push_back(p);
}
for(int i=0;i<N;i++)
{
if(h[h[i][0]][0]==i) nxt[i]=h[i][0]+n;
else nxt[i]=h[i][0];
if(h[i].size()>1)
{
if(h[h[i][1]][0]==i) nxt[i+n]=h[i][1]+n;
else nxt[i+n]=h[i][1];
}
else
{
if(h[h[i][0]][0]==i) nxt[i+n]=h[i][0]+n;
else nxt[i+n]=h[i][0];
}
d[0][i]=d[0][i+n]=d[1][i]=d[1][i+n]=-1;
}
for(int i=0;i<2*n;i++) g[nxt[i]].push_back(i);
dfs(P,0,0);
dfs(P+n,1,0);
for(int j=0;j<Q;j++)
{
int sol=0;
for(int i=0;i<N;i++) if(d[0][i]==G[j] || (d[0][i]>0 && d[0][P]>0 && d[0][i]<=G[j] && d[0][i]%d[0][P]==G[j]%d[0][P]) || d[1][i]==G[j] || (d[1][i]>0 && d[1][P+n]>0 && d[1][i]<=G[j] && d[1][i]%d[1][P+n]==G[j] % d[1][P+n])) sol++;
answer(sol);
}
}