| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1302820 | shivenbhargava | Tropical Garden (IOI11_garden) | C++20 | 0 ms | 0 KiB |
#include "garden.h"
#include "gardenlib.h"
#include "bits/stdc++.h"
using namespace std;
const int MAXN = 150007;
const int MAXM = 150007;
const int MAXQ = 2007;
const int MAXG = (int) 1e9+7;
const int MAXL = 30;
int Rf[MAXN];
int Rs[MAXN];
int succreal[MAXN][MAXL+1];
int succfake[MAXN][MAXL+1];
bool _second_path_real[MAXN][MAXL+1];
bool _second_path_fake[MAXN][MAXL+1];
bool succ(int x, int k, int p)
{
int ans = x;
bool fake = false;
int cur = pow(2,MAXL);
int curval = 30;
while (k!=0) {
while (cur>k) cur/=2,curval--;
k-=cur;
if (!fake) {
if (_second_path_real[ans][curval]) fake = true;
ans = succreal[ans][curval];
} else {
if (_second_path_fake[ans][curval]) fake = false;
ans = succfake[ans][curval];
}
}
return (ans == p);
}
void count_routes(int n, int m, int p, int R[][2], int q, int G[])
{
fill(Rf,Rf+MAXM,-1);
fill(Rs,Rs+MAXM,-1);
for (int i = 0; i<m; i++) {
int x = R[i][0], y = R[i][1];
if (Rf[x] == -1) Rf[x] = y;
else if (Rs[x] == -1) Rs[x] = y;
if (Rf[y] == -1) Rf[y] = x;
else if (Rs[y] == -1) Rs[y] = x;
}
for (int i = 0; i<n; i++) if (Rs[i] == -1) Rs[i] = Rf[i];
for (int i = 0; i<=MAXL; i++) {
for (int j = 0; j<n; j++) {
if (i == 0) {
succreal[j][i] = Rf[j];
if (Rf[Rf[j]] == j) _second_path_real[j][i] = true;
} else {
if (_second_path_real[j][i-1]) {
succreal[j][i] = succfake[succreal[j][i-1]][i-1];
_second_path_real[j][i] = _second_path_fake[succreal[j][i-1]][i-1];
} else {
succreal[j][i] = succreal[succreal[j][i-1]][i-1];
_second_path_real[j][i] = _second_path_real[succreal[j][i-1]][i-1];
}
}
if (i == 0) {
succfake[j][i] = Rs[j];
if (Rf[Rs[j]] == j) _second_path_fake[j][i] = true;
} else {
if (_second_path_fake[j][i-1]) {
succfake[j][i] = succfake[succfake[j][i-1]][i-1];
_second_path_fake[j][i] = _second_path_fake[succfake[j][i-1]][i-1];
} else {
succfake[j][i] = succreal[succfake[j][i-1]][i-1];
_second_path_fake[j][i] = _second_path_real[succfake[j][i-1]][i-1];
}
}
}
}
for (int i = 0; i<q; i++) for (int j = 0; j<n; j++) if (succ(j,G[i],p)) ans[i]++;
for (int i = 0; i<q; i++) answer(ans[i]);
return;
}