제출 #1076417

#제출 시각아이디문제언어결과실행 시간메모리
1076417ArthuroWich열대 식물원 (Tropical Garden) (IOI11_garden)C++17
100 / 100
1363 ms76276 KiB
#include "garden.h" #include "gardenlib.h" #include<bits/stdc++.h> using namespace std; int n, m, p, ans = 0; vector<int> adj[150005], radj[300005]; int succ[300005][31], vis1[300005], vis2[300005], dep1[300005], dep2[300005], cyc1 = -1, cyc2 = -1; void initsucc() { for (int j = 1; j < 31; j++) { for (int i = 0; i <= 2*n; i++) { succ[i][j] = succ[succ[i][j-1]][j-1]; } } } void calc(int a, int k) { for (int i = 0; i < 31; i++) { if (k & (1 << i)) { a = succ[a][i]; } } if (a == p || a == p+n) { ans++; } } void dfs1(int i, int st, int d) { if (vis1[i] && st == i && cyc1 == -1) { cyc1 = d; return; } if (vis1[i]) { return; } vis1[i] = 1; dep1[i] = d; for (int j : radj[i]) { dfs1(j, st, d+1); } } void dfs2(int i, int st, int d) { if (vis2[i] && st == i && cyc2 == -1) { cyc2 = d; return; } if (vis2[i]) { return; } vis2[i] = 1; dep2[i] = d; for (int j : radj[i]) { dfs2(j, st, d+1); } } void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) { n = N, m = M, p = P; for (int i = 0; i < m; i++) { if (adj[R[i][0]].size() < 2) { adj[R[i][0]].push_back(R[i][1]); } if (adj[R[i][1]].size() < 2) { adj[R[i][1]].push_back(R[i][0]); } } for (int i = 0; i < n; i++) { if (adj[i].size() == 1) { if (i == adj[adj[i][0]][0]) { succ[i][0] = adj[i][0]+n; } else { succ[i][0] = adj[i][0]; } succ[i+n][0] = succ[i][0]; } else { if (i == adj[adj[i][0]][0]) { succ[i][0] = adj[i][0]+n; } else { succ[i][0] = adj[i][0]; } if (i == adj[adj[i][1]][0]) { succ[i+n][0] = adj[i][1]+n; } else { succ[i+n][0] = adj[i][1]; } } } initsucc(); if (Q == 1) { ans = 0; for (int i = 0; i < n; i++) { calc(i, G[0]); } answer(ans); return; } for (int i = 0; i < 2*n; i++) { radj[succ[i][0]].push_back(i); } dfs1(p, p, 0); dfs2(p+n, p+n, 0); for (int j = 0; j < Q; j++) { ans = 0; for (int i = 0; i < n; i++) { bool f1 = 0, f2 = 0; int k = G[j]; if (vis1[i]) { k -= dep1[i]; if (k == 0) { f1 = 1; } else if (cyc1 != -1 && k % cyc1 == 0) { f1 = 1; } } k = G[j]; if (vis2[i]) { k -= dep2[i]; if (k == 0) { f2 = 1; } else if (cyc2 != -1 && k % cyc2 == 0) { f2 = 1; } } if (f1 || f2) { ans++; } } answer(ans); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...