제출 #999365

#제출 시각아이디문제언어결과실행 시간메모리
999365popu열대 식물원 (Tropical Garden) (IOI11_garden)C++17
100 / 100
1392 ms35668 KiB
#include "garden.h" #include "gardenlib.h" #include <bits/stdc++.h> #define f first #define s second using namespace std; vector<vector<int>> graf, auxgraf; int p, n, m, v1[300005], v2[300005], c, cycle1, cycle2; void afis() { for(int i = 0; i < 2 * n; i++) { if(i % 2) cout << i / 2 << "' : "; else cout << i / 2 << " : "; if(graf[i].size()) { if(graf[i][0] % 2) cout << graf[i][0] / 2 << "'"; else cout << graf[i][0] / 2; } cout << '\n'; } cout << '\n'; } int dfs1(int node) { if(!v1[node]) return 0; if(v1[node] > 0) return v1[node]; if(graf[node].size()) { v1[node] = 0; v1[node] = dfs1(graf[node][0]); if(v1[node] > 0) v1[node]++; return v1[node]; } return 0; } int dfs2(int node) { if(!v2[node]) return 0; if(v2[node] > 0) return v2[node]; if(graf[node].size()) { v2[node] = 0; v2[node] = dfs2(graf[node][0]); if(v2[node] > 0) v2[node]++; return v2[node]; } return 0; } int dfs3(int nodeStart) { int dist = 0, node; stack<int> s; s.push(nodeStart); v1[nodeStart] = 1; while(!s.empty()) { node = s.top(); s.pop(); v1[node] = 1; if(!graf[node].size()) return 0; if(graf[node][0] == nodeStart) return dist + 1; dist++; if(!v1[graf[node][0]]) s.push(graf[node][0]); } return 0; } void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) { p = P; n = N; m = M; graf.resize(2 * N + 1); auxgraf.resize(N + 1); for(int i = 0; i < 2 * N; i++) v2[i] = -1; for(int i = 0; i < M; i++) { if(auxgraf[R[i][0]].size() < 2) auxgraf[R[i][0]].push_back(R[i][1]); if(auxgraf[R[i][1]].size() < 2) auxgraf[R[i][1]].push_back(R[i][0]); } for(int i = 0; i < N; i++) { if(auxgraf[auxgraf[i][0]][0] == i && auxgraf[auxgraf[i][0]].size() > 1) graf[2 * i].push_back(2 * auxgraf[i][0] + 1); else graf[2 * i].push_back(2 * auxgraf[i][0]); if(auxgraf[i].size() == 2) { if(auxgraf[auxgraf[i][1]][0] == i && auxgraf[auxgraf[i][1]].size() > 1) graf[2 * i + 1].push_back(2 * auxgraf[i][1] + 1); else graf[2 * i + 1].push_back(2 * auxgraf[i][1]); } } //afis(); cycle1 = dfs3(P * 2); for(int i = 0; i < 2 * N; i++) v1[i] = 0; cycle2 = dfs3(P * 2 + 1); for(int i = 0; i < 2 * N; i++) v1[i] = -1; //cout << cycle1 << ' ' << cycle2 << '\n'; v1[P * 2] = 1; for(int i = 0; i < 2 * N; i++) { if(v1[i]) v1[i] = dfs1(i); } /* for(int i = 0; i < 2 * N; i++) { if(i % 2) cout << i / 2 << "' " << v1[i] << '\n'; else cout << i / 2 << " " << v1[i] << '\n'; } cout << '\n';*/ v2[P * 2 + 1] = 1; for(int i = 0; i < 2 * N; i++) { if(v2[i]) v2[i] = dfs2(i); } /* for(int i = 0; i < 2 * N; i++) { if(i % 2) cout << i / 2 << "' " << v2[i] << '\n'; else cout << i / 2 << " " << v2[i] << '\n'; }*/ for(int i = 0; i < Q; i++) { c = 0; for(int j = 0; j < 2 * N; j += 2) { if(v1[j] > 0 && !cycle1 && G[i] - v1[j] + 1 == 0) c++; else if(v2[j] > 0 && !cycle2 && G[i] - v2[j] + 1 == 0) c++; else if(G[i] - v2[j] + 1 >= 0 && v1[j] > 0 && cycle1 && (G[i] - v1[j] + 1) % cycle1 == 0) c++; else if(G[i] - v2[j] + 1 >= 0 && v2[j] > 0 && cycle2 && (G[i] - v2[j] + 1) % cycle2 == 0) c++; } answer(c); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...