| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 360916 | sean617 | 열대 식물원 (Tropical Garden) (IOI11_garden) | C++98 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "garden.h"
#include "gardenlib.h"
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#define N 150005
using namespace std;
int ty;
int n, m, st, cnt1, cnt, cnt2, fi[N], se[N], b[N][2][2], la[N][2], l[N][2];
bool v[N][2], v2[N][2], v3[N][2], ans[N];
vector<int> a[N], c[N][2][2];
void f(int p, int q) {
int t;
// if (v[p][q]) return;
// v[p][q] = 1;
if (q == 0) {
t = fi[p];
} else {
t = se[p];
}
b[p][q][0] = t;
b[p][q][1] = (fi[t] == p);
// f(t, (fi[t] == p));
}
void g(int p, int q) {
int i, cnt, t1, t2, j1, j2;
if (v2[p][q]) {
j1 = p;
j2 = q;
cnt = 0;
while (1) {
cnt++;
t1 = c[j1][j2][0][la[j1][j2]];
t2 = c[j1][j2][1][la[j1][j2]];
j1 = t1;
j2 = t2;
if (j1 == p && j2 == q) break;
}
if (ty == 0) cnt1 = cnt;
else cnt2 = cnt;
return;
}
v2[p][q] = 1;
for (i =0; i < c[p][q][0].size(); i++) {
la[p][q] = i;
g(c[p][q][0][i], c[p][q][1][i]);
}
}
void g2(int p, int q, int w) {
int i;
if (v3[p][q]) return;
v3[p][q] = 1;
if (q == 0) l[p][ty] = w;
for (i = 0; i < c[p][q][0].size(); i++) {
g2(c[p][q][0][i], c[p][q][1][i], w + 1);
}
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
int i, j, t, t1, t2;
// freopen ("input.txt", "r", stdin);
cin >> n >> m >> st;
n = N;
m = M;
st = P;
for (i = 0; i < m; i++) {
t1 = R[i][0];
t2 = R[i][1];
a[t1].push_back(t2);
a[t2].push_back(t1);
}
for (i = 0; i < n; i++) {
fi[i] = a[i][0];
if (a[i].size() == 1) se[i] = a[i][0];
else se[i] = a[i][1];
}
// for (i = 0; i < n; i++) {
// printf("%d %d\n", fi[i], se[i]);
// }
for (i = 0; i < n; i++) {
f(i, 0);
f(i, 1);
}
for (i = 0; i < n; i++) {
for (j = 0; j < 2; j++) {
c[b[i][j][0]][b[i][j][1]][0].push_back(i);
c[b[i][j][0]][b[i][j][1]][1].push_back(j);
// printf("%d %d %d %d\n", i, j, b[i][j][0], b[i][j][1]);
}
}
memset(l, -1, sizeof(l));
ty = 0;
cnt = 0;
g(st, 0);
g2(st, 0, 0);
memset(v2, 0, sizeof(v2));
memset(v3, 0, sizeof(v3));
ty = 1;
cnt = 0;
g(st, 1);
g2(st, 1, 0);
int anscnt;
while (Q--) {
t = G[i];
anscnt = 0;
for (i = 0; i < n; i++) {
if (t == l[i][0] || l[i][0] != -1 && t > l[i][0] && cnt1 > 0 && (t - l[i][0]) % cnt1 == 0) anscnt++;
else if (t == l[i][1] || l[i][1] != -1 && t > l[i][1] && cnt2 > 0 && (t - l[i][1]) % cnt2 == 0) anscnt++;
}
answer(anscnt);
}
}