Submission #598188

#TimeUsernameProblemLanguageResultExecution timeMemory
598188snasibov05Tropical Garden (IOI11_garden)C++14
100 / 100
2519 ms42108 KiB
#include "garden.h" #include "gardenlib.h" #include <bits/stdc++.h> using namespace std; void dfs(int cur, int t, vector<int>& d, int& c, vector<vector<int>>& ed){ for (auto to : ed[cur]){ if (to == t) { c = d[cur] + 1; continue; } d[to] = d[cur] + 1; dfs(to, t, d, c, ed); } } void count_routes(int n, int m, int p, int r[][2], int q, int g[]){ vector<vector<int>> ed(n, vector<int>(2, -1)); for (int i = 0; i < m; ++i) { if (ed[r[i][0]][0] == -1) ed[r[i][0]][0] = r[i][1]; else if (ed[r[i][0]][1] == -1) ed[r[i][0]][1] = r[i][1]; if (ed[r[i][1]][0] == -1) ed[r[i][1]][0] = r[i][0]; else if (ed[r[i][1]][1] == -1) ed[r[i][1]][1] = r[i][0]; } for (int i = 0; i < n; ++i) { if (ed[i][1] == -1) ed[i][1] = ed[i][0]; } vector<vector<int>> gg(2*n); for (int i = 0; i < n; ++i){ int t1 = ed[i][0]; if (ed[t1][0] == i) gg[t1 + n].push_back(i); else gg[t1].push_back(i); int t2 = ed[i][1]; if (ed[t2][0] == i) gg[t2 + n].push_back(i + n); else gg[t2].push_back(i + n); } vector<int> d1(2*n, 2*n + 5); d1[p] = 0; vector<int> d2(2*n, 2*n + 5); d2[p + n] = 0; int c1 = 2*n + 5, c2 = 2*n + 5; dfs(p, p, d1, c1, gg); dfs(p + n, p + n, d2, c2, gg); for (int i = 0; i < q; ++i){ int res = 0; for (int j = 0; j < n; ++j){ if (d1[j] == g[i] || (c1 <= 2*n && g[i] - d1[j] > 0 && d1[j] <= 2*n && (g[i] - d1[j]) % c1 == 0)) res++; else if (d2[j] == g[i] || (c2 <= 2*n && g[i] - d2[j] > 0 && d2[j] <= 2*n && (g[i] - d2[j]) % c2 == 0)) res++; } answer(res); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...