Submission #592700

#TimeUsernameProblemLanguageResultExecution timeMemory
592700MamedovTropical Garden (IOI11_garden)C++17
100 / 100
2615 ms27692 KiB
#pragma GCC optimize ("O3") #include "garden.h" #include "gardenlib.h" #include <bits/stdc++.h> #define pii pair<int, int> #define piii pair<pii, int> #define vi vector<int> #define vvi vector<vi> #define vpii vector<pii> #define vvpii vector<vpii> #define f first #define s second #define oo 1000000001 #define eb emplace_back #define pb push_back #define mpr make_pair #define size(v) (int)v.size() #define ln '\n' #define ull unsigned long long #define ll long long #define all(v) v.begin(), v.end() using namespace std; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); void dfs(int node, vvi &g, vi &dist, int &cycle) { for (int to : g[node]) { if (dist[to] == oo) { dist[to] = dist[node] + 1; dfs(to, g, dist, cycle); } else { cycle = dist[node] + 1; } } } void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) { vvi minTrail(2, vi(N, -1)); for (int i = 0; i < M; ++i) { for (int j = 0; j < 2; ++j) { int u = R[i][j]; if (minTrail[0][u] == -1) { minTrail[0][u] = i; } else if (minTrail[1][u] == -1) { minTrail[1][u] = i; } } } for (int i = 0; i < N; ++i) { if (minTrail[1][i] == -1) { minTrail[1][i] = minTrail[0][i]; } } vvi gt(2 * N); for (int i = 0; i < N; ++i) { for (int j = 0; j < 2; ++j) { int trail = minTrail[j][i]; int node = R[trail][0] + R[trail][1] - i; if (minTrail[0][node] == trail) { node += N; } gt[node].eb(i + j * N); } } vi cycle(2, 0); vvi dist(2, vi(2 * N, oo)); dist[0][P] = 0; dfs(P, gt, dist[0], cycle[0]); dist[1][P + N] = 0; dfs(P + N, gt, dist[1], cycle[1]); for (int i = 0; i < Q; ++i) { int cnt = 0; for (int j = 0; j < N; ++j) { if (dist[0][j] == G[i] || (cycle[0] && G[i] > dist[0][j] && (G[i] - dist[0][j]) % cycle[0] == 0)) { ++cnt; } else if (dist[1][j] == G[i] || (cycle[1] && G[i] > dist[1][j] && (G[i] - dist[1][j]) % cycle[1] == 0)) { ++cnt; } } answer(cnt); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...