Submission #602287

#TimeUsernameProblemLanguageResultExecution timeMemory
602287patrikpavic2Game (APIO22_game)C++17
30 / 100
4094 ms28088 KiB
#include "game.h" #include <vector> #include <cstdio> #define PB push_back using namespace std; const int N = 5e5 + 500; const int BUK = 400; int n, k, ans; vector < int > v[N], r[N]; int L[N], R[N], bukL[N], bukR[N], rac[N], bio[N], cookie; void init(int _n, int _k) { n = _n, k = _k; for(int i = 0;i < n;i++) L[i] = -1, R[i] = n, bukL[i] = -1, bukR[i] = k; for(int i = 0;i < k;i++) L[i] = i, R[i] = i, bukL[i] = i / BUK, bukR[i] = i / BUK, rac[i] = 1; } void buk_noviL(int x, int vr){ bukL[x] = vr; for(int y : v[x]) if(bukL[y] < vr) buk_noviL(y, vr); } void buk_noviR(int x, int vr){ bukR[x] = vr; for(int y : r[x]) if(bukR[y] > vr) buk_noviR(y, vr); } void noviL(int x, int vr){ L[x] = vr; for(int y : v[x]) if(L[y] < vr && bukR[y] <= vr / BUK) noviL(y, vr); } void stariL(int x){ if(bio[x] == cookie) return; bio[x] = cookie; for(int y : r[x]){ if(bukL[y] < bukL[x]) continue; stariL(y); L[x] = max(L[x], L[y]); } } void stariR(int x){ if(bio[x] == cookie) return; bio[x] = cookie; for(int y : v[x]){ if(bukR[y] > bukR[x]) continue; stariR(y); R[x] = min(R[x], R[y]); } } void noviR(int x, int vr){ R[x] = vr; for(int y : r[x]) if(R[y] > vr && bukL[y] >= vr / BUK) noviR(y, vr); } void update(int a){ if(bukL[a] == bukR[a] && !rac[a]){ cookie++; stariL(a); cookie++; stariR(a); //rac[a] = 1; } } int add_teleporter(int a, int b) { v[a].PB(b), r[b].PB(a); if(a == b && a < k) ans = 1; if(bukL[b] < bukL[a]) buk_noviL(b, bukL[a]); if(bukR[a] > bukR[b]) buk_noviR(a, bukR[b]); ans |= bukL[a] > bukR[a]; ans |= bukL[b] > bukR[b]; if(L[b] < L[a] && bukR[b] <= L[a] / BUK) noviL(b, L[a]); if(R[a] > R[b] && bukL[a] >= R[b] / BUK) noviR(a, R[b]); update(a); update(b); if(a >= k) ans |= L[a] == R[a]; if(b >= k) ans |= L[b] == R[b]; ans |= L[a] > R[a]; ans |= L[b] > R[b]; return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...