Submission #1114282

#TimeUsernameProblemLanguageResultExecution timeMemory
1114282usukhbaatarTropical Garden (IOI11_garden)C++17
0 / 100
2 ms336 KiB
#include <bits/stdc++.h> #include "garden.h" #include "gardenlib.h" using namespace std; int n, m, fn; vector<vector<pair<int, int>>> a; vector<int> g; vector<bool> vis; vector<bool> start; vector<bool> finish; int kk = 0; int ans = 0; void dfs(int u, int p, int i, int depth) { if (depth == kk) { if (u == fn) ans++; return; } int x = (i << 1) + (p > u); //if (x >= 0 && vis[x]) return; if (x != -1) vis[x] = 1; if (a[u].size() == 0) return; if (i != -1 && u == fn) finish[x] = 1; int id = (a[u].size() == 1 || a[u][0].second != i) ? 0 : 1; int v = a[u][id].first; int j = a[u][id].second; int y = (j << 1) + (v < u); if (x != -1) { if (g[x] != -1 && g[x] != y) exit(1); g[x] = y; } else start[y] = 1; dfs(v, u, j, depth + 1); } bool check(int u, int k) { for (int i = 0; i < k - 1; i++) { u = g[u]; if (u == -1) return 0; } return finish[u]; } void count_routes(int N, int M, int P, int ed[][2], int q, int qry[]) { n = N, m = (M << 1), fn = P; a.resize(n); vis.resize(m, 0); g.resize(m, -1); start.resize(m, 0); finish.resize(m, 0); cout << q << endl; for (int i = 0; i < n; i++) { int u = ed[i][0], v = ed[i][1]; if (a[u].size() < 2) a[u].push_back({v, i}); if (a[v].size() < 2) a[v].push_back({u, i}); } kk = qry[0]; for (int u = 0; u < n; u++) { dfs(u, n, -1, 0); } answer(ans); return; for (int i = 0; i < q; i++) { int ans = 0; for (int u = 0; u < m; u++) { if (start[u] && check(u, qry[i])) { ans++; } } answer(ans); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...