| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 116605 | nvmdava | Tropical Garden (IOI11_garden) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "garden.h"
#include "gardenlib.h"
int best[150001][2];
int cyc;
int len[150001];
int time[150001][2];
bool in[150001];
bool proc[150001];
bool doing[150001];
int dfs(int v){
if(proc[v]) return time[v][1];
if(doing[v] == 1) return 1000000001;
doing[v] = 1;
time[v][1] = dfs(best[v][1]) + 1;
doing[v] = 0;
proc[v] = 1;
return time[v][1];
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[]){
for(int i = 0; i < M; i++){
int v = R[i][0], v = R[i][1];
if(!best[v][0]) best[v][0] = u;
else if(!best[v][1]) best[v][1] = u;
if(!best[u][0]) best[u][0] = v;
else if(!best[u][1]) best[u][1] = v;
}
for(int i = 0; i < N; i++)
if(!best[i][1]) best[i][1] = best[i][0];
int now = P;
while(!in[now]) {
in[now] = 1;
cyc++;
now = best[now][1];
}
if(now != P)
cyc = 1000000001;
proc[P] = 1;
for(int i = 0; i < N; i++)
if(!proc[i])dfs(i);
for(int i = 0; i < N; i++){
time[i][1] = time[best[i][0]] + 1;
if(time[i][1] <= 150000)
len[time[i][1]]++;
}
for(int i = cyc; i <= N; i++)
len[i] += len[i - cyc];
for(int i = 0; i < Q; i++){
if(G[i] > N){
G[i] = N - ((cyc - G[i] % cyc) % cyc);
}
answer(len[G[i]]);
}
}