Submission #551234

#TimeUsernameProblemLanguageResultExecution timeMemory
551234ymmTropical Garden (IOI11_garden)C++17
49 / 100
116 ms42676 KiB
/// /// There's a reason for your defeat, DIO. One simple reason... /// You pissed me off. /// #include <bits/stdc++.h> #define Loop(x,l,r) for(ll x = ll(l); x < ll(r); ++x) #define LoopR(x,l,r) for(ll x = ll(r)-1; x >= ll(l); --x) #define Kill(x) exit((cout << (x) << '\n', 0)) typedef long long ll; typedef std::pair<int,int> pii; typedef std::pair<ll,ll> pll; using namespace std; #ifndef DARD #include "garden.h" #include "gardenlib.h" #else void answer(int x) { cout << x << ' '; } #endif const int N = 150'010; vector<int> T[2*N]; int A[2*N]; int deg[2*N], cnt[2*N]; void add_edge(int v, int u) { A[v] = u; T[u].push_back(v); } int ans[N]; int q, g[N]; bool cyc[2*N]; void dfs(int v, int d) { cnt[d] += v >= N; for (int u : T[v]) dfs(u, d+1); } vector<int> vmod[2*N]; int cycs; void dfs2(int v, int d, int rt) { if (v >= N) vmod[d%cycs].push_back(d); for (int u : T[v]) if (u != rt) dfs2(u, d+1, rt); } void solve(int v) { memset(cyc, 0, sizeof(cyc)); int u = v; cycs = 0; do { cyc[u] = 1; u = A[u]; ++cycs; } while (!cyc[u]); if (u != v) { memset(cnt, 0, sizeof(cnt)); dfs(v, 0); Loop (i,0,q) ans[i] += cnt[g[i]]; } else { Loop (i,0,cycs) vmod[i].clear(); dfs2(v, 0, v); Loop (i,0,cycs) sort(vmod[i].begin(), vmod[i].end()); Loop (i,0,q) { int gm = g[i]%cycs; ans[i] += upper_bound(vmod[gm].begin(), vmod[gm].end(), g[i]) - vmod[gm].begin(); } } } void count_routes(int n, int m, int p, int r[][2], int q, int g[]) { Loop (i,0,m) { deg[r[i][0]]++; deg[r[i][1]]++; } Loop (i,0,m) { for (auto [v, u] : {pii{r[i][0], r[i][1]}, pii{r[i][1], r[i][0]}}) { if ((cnt[v] == 1 || deg[v] == 1) && cnt[u] == 0) // F F add_edge(v, u); if ((cnt[v] == 1 || deg[v] == 1) && cnt[u] != 0) // F nF add_edge(v, u+N); if (cnt[v] == 0 && cnt[u] == 0) // nF F add_edge(v+N, u); if (cnt[v] == 0 && cnt[u] != 0) // nF nF add_edge(v+N, u+N); } cnt[r[i][0]]++; cnt[r[i][1]]++; } ::q = q; Loop (i,0,q) ::g[i] = g[i]; solve(p); solve(p+N); Loop (i,0,q) answer(ans[i]); } #ifdef DARD int main() { // int constexpr n = 6; // int constexpr m = 6; // int constexpr p = 0; // int constexpr q = 1; // int g[q] = {3}; // int r[m][2] = {{1,2}, {0,1}, {0,3}, {3,4}, {4,5}, {1,5}}; int constexpr n = 5; int constexpr m = 5; int constexpr p = 2; int constexpr q = 2; int g[q] = {3, 1}; int r[m][2] = {{1,0}, {1,2}, {3,2}, {1,3}, {4,2}}; count_routes(n, m, p, r, q, g); cout << '\n'; } #endif
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...