Submission #707233

#TimeUsernameProblemLanguageResultExecution timeMemory
707233Nhoksocqt1Tropical Garden (IOI11_garden)C++17
69 / 100
5040 ms53848 KiB
#include<bits/stdc++.h> #include "garden.h" #include "gardenlib.h" using namespace std; #define inf 0x3f3f3f3f #pragma GCC target ("avx2") #pragma GCC optimization ("O3") #pragma GCC optimization ("unroll-loops") #define sz(x) int((x).size()) #define fi first #define se second typedef long long ll; typedef pair<int, int> ii; template<class X, class Y> inline bool maximize(X &x, const Y &y) {return (x < y ? x = y, 1 : 0);} template<class X, class Y> inline bool minimize(X &x, const Y &y) {return (x > y ? x = y, 1 : 0);} mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); int Random(int l, int r) { return uniform_int_distribution<int>(l, r)(rng); } const int MAXN = 150005; struct Edge { int u, v; } edge[MAXN]; vector<ii> adj[MAXN]; vector<int> comp[2 * MAXN]; int firstToLoop[2 * MAXN], firstInLoop[2 * MAXN], loopOf[2 * MAXN], posInComp[2 * MAXN]; int deg[2 * MAXN], pa[2 * MAXN], P[2 * MAXN][19], idc[2 * MAXN], idn[2 * MAXN], numNode, numEdge, numQuery, lastNode; bool dx[2 * MAXN]; inline int getLeftNode(int id) { return (id >= numEdge) ? edge[id - numEdge].v : edge[id].u; } int getLCA(int u, int k) { for (int i1 = k; i1 > 0; i1 ^= i1 & -i1) { int i = __builtin_ctz(i1 & -i1); u = P[u][i]; } return u; } void count_routes(int _N, int _M, int _P, int _R[][2], int _Q, int _G[]) { numNode = _N, numEdge = _M, lastNode = _P, numQuery = _Q; for (int i = 0; i < _M; ++i) { int u(_R[i][0]), v(_R[i][1]); edge[i] = {u, v}; adj[u].push_back({v, i}); adj[v].push_back({u, i}); } for (int u = 0; u < numNode; ++u) { int id0 = adj[u][0].se; int id1 = (adj[u].size() > 1 ? adj[u][1].se : 1e9+7); bool type0 = (u == edge[adj[u][0].se].v); bool type1 = (adj[u].size() > 1 && (u == edge[adj[u][1].se].v)); for (int it = 0; it < int(adj[u].size()); ++it) { int v(adj[u][it].fi), id(adj[u][it].se); bool type = !(u == edge[id].v); if(it == 0) idn[u] = id + !type * numEdge; pa[id + type * numEdge] = (id != id0 || id1 >= 1e9+7) ? id0 + type0 * numEdge : id1 + type1 * numEdge; ++deg[pa[id + type * numEdge]]; P[id + type * numEdge][0] = pa[id + type * numEdge]; //cout << id + type * numEdge << ' ' << pa[id + type * numEdge] << '\n'; } } for (int j = 1; j < 19; ++j) { for (int i = 0; i < 2 * numEdge; ++i) { P[i][j] = P[P[i][j - 1]][j - 1]; } } int numComp(0); for (int id = 0; id < 2 * numEdge; ++id) { if(deg[id] || dx[id]) continue; vector<int> tmpn; int tmp(id); while(!dx[tmp]) { dx[tmp] = 1; tmpn.push_back(tmp); tmp = pa[tmp]; } int szn(tmpn.size()); //cout << szn << '\n'; for (int it = 0; it <= szn; ++it) { if(it == szn || tmpn[it] == tmp) { if(it < szn) { //cout << "LOOP COMP: "; for (int jt = it; jt < szn; ++jt) { posInComp[tmpn[jt]] = jt - it; comp[numComp].push_back(tmpn[jt]); firstInLoop[tmpn[jt]] = tmpn[jt]; loopOf[tmpn[jt]] = szn - it; firstToLoop[tmpn[jt]] = 0; idc[tmpn[jt]] = numComp; //cout << tmpn[jt] << " \n"[jt + 1 == szn]; } ++numComp; } if(it > 0) { //cout << "COMP TO " << firstInLoop[tmp] << ": "; for (int jt = 0; jt < it; ++jt) { posInComp[tmpn[jt]] = jt; comp[numComp].push_back(tmpn[jt]); firstToLoop[tmpn[jt]] = it - jt + firstToLoop[tmp]; firstInLoop[tmpn[jt]] = firstInLoop[tmp]; idc[tmpn[jt]] = numComp; //cout << tmpn[jt] << " \n"[jt + 1 == it]; } //cout << '\n'; ++numComp; } break; } } } for (int id = 0; id < 2 * numEdge; ++id) { if(!deg[id] || dx[id]) continue; int tmp(id); while(!dx[tmp]) { dx[tmp] = 1; posInComp[tmp] = comp[numComp].size(); comp[numComp].push_back(tmp); idc[tmp] = numComp; firstToLoop[tmp] = 0; firstInLoop[tmp] = tmp; tmp = pa[tmp]; } int szn(comp[numComp].size()); for (int it = 0; it < szn; ++it) loopOf[comp[numComp][it]] = szn; /*cout << "LOOP COMP: "; for (int it = 0; it < szn; ++it) cout << comp[numComp][it] << " \n"[it + 1 == szn];*/ ++numComp; } for (int t = 0; t < numQuery; ++t) { int K(_G[t]), cnt(0); //cout << K << ": "; for (int u = 0; u < numNode; ++u) { int id(idn[u]); if(K < firstToLoop[id]) { cnt += (getLeftNode(getLCA(id, K)) == lastNode); continue; } int kNow(K - firstToLoop[id]); id = firstInLoop[id]; //cout << '.' << id << '\n'; //continue; cnt += (getLeftNode(comp[idc[id]][(posInComp[id] + kNow) % loopOf[id]]) == lastNode); } answer(cnt); } }

Compilation message (stderr)

garden.cpp:8: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    8 | #pragma GCC optimization ("O3")
      | 
garden.cpp:9: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    9 | #pragma GCC optimization ("unroll-loops")
      | 
garden.cpp: In function 'void count_routes(int, int, int, int (*)[2], int, int*)':
garden.cpp:67:17: warning: unused variable 'v' [-Wunused-variable]
   67 |             int v(adj[u][it].fi), id(adj[u][it].se);
      |                 ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...