제출 #263338

#제출 시각아이디문제언어결과실행 시간메모리
263338Berted열대 식물원 (Tropical Garden) (IOI11_garden)C++14
100 / 100
234 ms58616 KiB
#include "garden.h" #include "gardenlib.h" #include <vector> #include <assert.h> #include <iostream> #include <algorithm> #define vi vector<int> const int INF = 1e9; using namespace std; vi sadj[150001], adj[300001]; int dst[2][300001], cyc[2]; vi ans[2][300001]; void DFS(int u, int id) { // cout << u << " " << id << " " << dst[id][u] << "\n"; for (auto v : adj[u]) { if (dst[id][v] == INF) { dst[id][v] = dst[id][u] + 1; DFS(v, id); } else { assert(cyc[id] == -1 && dst[id][v] == 0); cyc[id] = dst[id][u] + 1; } } } /* It is possible to represent the problem as a digraph with 2N nodes such that each node has at most one outgoing edge. We can use this property to determine which cycle lengths are valid. */ void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) { for (int i = 0; i < M; i++) { sadj[R[i][0]].push_back(R[i][1]); sadj[R[i][1]].push_back(R[i][0]); } cyc[0] = cyc[1] = -1; for (int u = 0; u < N; u++) { for (int j = 0; j < min(2, (int)sadj[u].size()); j++) { int v = sadj[u][j]; //cout << "Add edge " << 2 * u + j << " -> " << 2 * v + (sadj[v].size() > 1 && u == sadj[v][0]) << "\n"; adj[2 * v + (sadj[v].size() > 1 && u == sadj[v][0])].push_back(2 * u + j); } } for (int i = 0; i < 2 * N; i++) {dst[0][i] = dst[1][i] = INF;} for (int i = 0; i < 2; i++) { dst[i][2 * P + i] = 0; DFS(2 * P + i, i); if (cyc[i] == -1) { for (int j = 0; j < 2 * N; j += 2) { if (dst[i][j] < INF) ans[i][0].push_back(dst[i][j]); } sort(ans[i][0].begin(), ans[i][0].end()); } else { for (int j = 0; j < 2 * N; j += 2) { if (dst[i][j] < INF) ans[i][dst[i][j] % cyc[i]].push_back(dst[i][j]); } for (int j = 0; j < cyc[i]; j++) { sort(ans[i][j].begin(), ans[i][j].end()); } } } for (int i = 0; i < Q; i++) { int ret = 0; for (int j = 0; j < 2; j++) { if (cyc[j] == -1) { ret += upper_bound(ans[j][0].begin(), ans[j][0].end(), G[i]) - lower_bound(ans[j][0].begin(), ans[j][0].end(), G[i]); } else { int v = G[i] % cyc[j]; ret += upper_bound(ans[j][v].begin(), ans[j][v].end(), G[i]) - ans[j][v].begin(); } } answer(ret); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...