Submission #588622

#TimeUsernameProblemLanguageResultExecution timeMemory
588622MilosMilutinovicTropical Garden (IOI11_garden)C++14
100 / 100
4593 ms74412 KiB
/** * author: wxhtzdy * created: 03.07.2022 18:28:39 **/ #include "garden.h" #include "gardenlib.h" #include <bits/stdc++.h> using namespace std; void count_routes(int n, int m, int p, int r[][2], int q, int k[]) { vector<vector<pair<int, int>>> e(n); for (int i = 0; i < m; i++) { if ((int) e[r[i][0]].size() < 2) { e[r[i][0]].emplace_back(i, r[i][1]); } if ((int) e[r[i][1]].size() < 2) { e[r[i][1]].emplace_back(i, r[i][0]); } } for (int i = 0; i < n; i++) { if ((int) e[i].size() == 1) { e[i].push_back(e[i][0]); } assert((int) e[i].size() == 2); } vector<vector<int>> g(2 * n); vector<vector<int>> f(2 * n); function<void(int, int)> Add = [&](int v, int u) { g[v].push_back(u); f[u].push_back(v); }; for (int i = 0; i < n; i++) { if (e[i][0].first == e[e[i][0].second][0].first) { Add(i * 2, e[i][0].second * 2 + 1); } else { Add(i * 2, e[i][0].second * 2); } if (e[i][1].first == e[e[i][1].second][0].first) { Add(i * 2 + 1, e[i][1].second * 2 + 1); } else { Add(i * 2 + 1, e[i][1].second * 2); } } vector<int> in(2 * n); for (int i = 0; i < 2 * n; i++) { in[g[i][0]] += 1; } vector<int> que; for (int i = 0; i < 2 * n; i++) { if (in[i] == 0) { que.push_back(i); } } for (int b = 0; b < (int) que.size(); b++) { int i = que[b]; for (int j : g[i]) { in[j] -= 1; if (in[j] == 0) { que.push_back(j); } } } vector<vector<pair<int, int>>> opt(2 * n); if (in[2 * p] == 0) { function<void(int, int)> Dfs = [&](int v, int dep) { opt[v].emplace_back(dep, 1e9 + 1); for (int u : f[v]) { Dfs(u, dep + 1); } }; Dfs(2 * p, 0); } if (in[2 * p + 1] == 0) { function<void(int, int)> Dfs = [&](int v, int dep) { opt[v].emplace_back(dep, 1e9 + 1); for (int u : f[v]) { Dfs(u, dep + 1); } }; Dfs(2 * p + 1, 0); } for (int ver = 0; ver < 2 * n; ver++) { if (in[ver] == 0) { continue; } que = vector<int>(1, ver); for (int b = 0; b < (int) que.size(); b++) { int i = que[b]; for (int j : g[i]) { in[j] -= 1; if (in[j] == 0 && j != ver) { que.push_back(j); } } } for (int i : que) { if (i == 2 * p) { function<void(int, int)> Dfs = [&](int v, int dep) { opt[v].emplace_back(dep, (int) que.size()); for (int u : f[v]) { if (u != 2 * p) { Dfs(u, dep + 1); } } }; Dfs(i, 0); } } for (int i : que) { if (i == 2 * p + 1) { function<void(int, int)> Dfs = [&](int v, int dep) { opt[v].emplace_back(dep, (int) que.size()); for (int u : f[v]) { if (u != 2 * p + 1) { Dfs(u, dep + 1); } } }; Dfs(i, 0); } } } for (int i = 0; i < q; i++) { int cnt = 0; for (int j = 0; j < n; j++) { int add = 0; for (auto& p : opt[2 * j]) { if (p.first > k[i]) { continue; } if ((k[i] - p.first) % p.second == 0) { add = 1; } } cnt += add; } answer(cnt); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...