# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
103456 | popovicirobert | 열대 식물원 (Tropical Garden) (IOI11_garden) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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);
}
}