# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
103456 | popovicirobert | Tropical Garden (IOI11_garden) | C++14 | 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>
#include "garden.h"
using namespace std;
typedef vector <int> VI;
typedef vector <VI> VVI;
typedef pair <int, int> PII;
typedef vector <PII> VPII;
typedef vector <VPII> VVPII;
void count_routes(int n, int m, int p, int R[][2], int q, int G[]) {
VVI g(n + 1);
int i;
for(i = 0; i < m; i++) {
R[i][0]++, R[i][1]++;
g[R[i][0]].push_back(i);
g[R[i][1]].push_back(i);
}
for(i = 1; i <= n; i++) {
sort(g[i].begin(), g[i].end());
}
VVI anc(2 * n + 1, VI(30));
for(i = 1; i <= n; i++) {
int nod = (R[g[i][0]][0] ^ R[g[i][0]][1] ^ i);
if(g[nod][0] == g[i][0]) {
anc[i][0] = nod + n;
}
else {
anc[i][0] = nod;
}
if(g[i].size() == 1) {
if(g[nod][0] == g[i][0]) {
anc[i + n][0] = nod + n;
}
else {
anc[i + n][0] = nod;
}
}
else {
nod = (R[g[i][1]][0] ^ R[g[i][1]][1] ^ i);
if(g[nod][0] == g[i][1]) {
anc[i + n][0] = nod + n;
}
else {
anc[i + n][0] = nod;
}
}
}
for(int bit = 1; bit < 30; bit++) {
for(i = 1; i <= 2 * n; i++) {
anc[i][bit] = anc[anc[i][bit - 1]][bit - 1];
}
}
p++;
for(int t = 0; t < q; t++) {
int ans = 0;
for(i = 1; i <= n; i++) {
int nod = i;
for(int bit = 0; (1 << bit) <= G[t]; bit++) {
if(G[t] & (1 << bit)) {
nod = anc[nod][bit];
/*if(i == 1) {
cerr << nod << " ";
}*/
}
}
if(nod == p || nod == n + p) {
ans++;
}
}
answer(ans);
}
}