| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 786633 | allin27x | 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;
int gl;
int ps[(int)15e4+2][2];
int vis[(int)15e4+2][2];
int ds[(int)15e4+2][2];
int gd[(int)15e4+2][2];
int a1 = 0; int a2 = 0;
int g1 = 0; int g2 = 0;
int dfs1(int p, int last, int len){
int nx;
if (last == ps[p][0]) nx = 1;
else nx = 0;
if (p==gl) return len * (2*nx-1);
if (vis[p][nx]) return (int)1e7;
vis[p][nx] = 1;
dfs1(ps[p][nx], p, len+1);
}
void answer(int x);
void answer(int x){
cout<<x<<' ';
}
void dfs2(int p, int last){
int nx; if (last == ps[p][0]) nx = 1; else nx = 0;
if (p == gl){
gd[p][nx] = nx;
ds[p][nx] = 0;
return;
}
if (ds[p][nx]) return;
if (vis[p][nx]){
ds[p][nx] = (int)-1e5;
return;
}
vis[p][nx] = 1;
int nxt = ps[p][nx];
int d; if (p == ps[nxt][0]) d = 1; else d = 0;
dfs2(nxt, p);
gd[p][nx] = gd[nxt][d];
ds[p][nx] = ds[nxt][d]+1;
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[]){
gl = P;
for (int i=0; i<N; i++) ps[i][0]=-1, ps[i][1]=-1;
for (int i=0; i<M; i++){
int a = R[i][0]; int b= R[i][1];
if (ps[a][0]==-1) ps[a][0] = b; else if (ps[a][1]==-1) ps[a][1] = b;
if (ps[b][0]==-1) ps[b][0] = a; else if (ps[b][1]==-1) ps[b][1] = a;
}
for (int i=0; i<N; i++) if (ps[i][1]==-1) ps[i][1] = ps[i][0];
for (int i=0; i<N; i++) vis[i][0] = 0, vis[i][1] = 0;
int r1 = dfs1(ps[P][0], P, 1);
for (int i=0; i<N; i++) vis[i][0] = 0, vis[i][1] = 0;
int r2 = dfs1(ps[P][1], P, 1);
if (r1!=1e7) {
if (r1>0) g1 = 1;
a1 = abs(r1);
}
if (r2!=1e7){
if (r2>0) g2 = 1;
a2 = abs(r2);
}
for (int i=0; i<N; i++) vis[i][0] = 0, vis[i][1] = 0;
for (int i=0; i<N; i++) ds[i][0] = 0, ds[i][1] = 0;
for (int i=0; i<N; i++) {
if (i==P) continue;
if (!ds[i][0]) dfs2(i, -1);
}
for (int q = 0; q<Q; q++){
int k = G[q];
int ans = 0;
for (int i=0; i<N; i++){
if (ds[i][0] < 0) continue;
if (k<ds[i][0]) continue;
int t= k - ds[i][0];
if (gd[i][0]==0){
if (a1 == 0) continue;
if (g1 == 0 && t%a1 == 0) ans++;
if (g1 == 1 && a2 == 0 && (t==0 || t==a1)) ans++;
if (g1 == 1 && g2 == 0 && (t%(a1+a2)==0 || t%(a1+a2)==a1)) ans++;
if (g1 == 1 && g2 == 1 && (t==0 || (t-a1)&a2 == 0)) ans++;
} else {
swap(a1,a2); swap(g1,g2);
if (a1 == 0) continue;
if (g1 == 0 && t%a1 == 0) ans++;
if (g1 == 1 && a2 == 0 && (t==0 || t==a1)) ans++;
if (g1 == 1 && g2 == 0 && (t%(a1+a2)==0 || t%(a1+a2)==a1)) ans++;
if (g1 == 1 && g2 == 1 && (t==0 || (t-a1)&a2 == 0)) ans++;
swap(a1,a2); swap(g1,g2);
}
}
answer(ans);
}
}
int main(){
int n = 5; int m = 5;
int p=2;int q = 2; int g[] = {3,1};
int r[][2]= {
{1,0},
{1,2},
{3,2},
{1,3},
{4,2}
};
count_routes(n,m,p,r,q,g);
// cout<<'\n';
// for (int i=0; i<n; i++){
// cout<<i<<' '<<jump(i, 4)<<'\n';
// }
}