Submission #602284

#TimeUsernameProblemLanguageResultExecution timeMemory
602284patrikpavic2Game (APIO22_game)C++17
12 / 100
16 ms23952 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], pos[N], kad[N], tme, SAD, tocL[N], tocR[N]; 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] = n, pos[i] = -1; for(int i = 0;i < k;i++) L[i] = i, R[i] = i, bukL[i] = i / BUK, bukR[i] = i / BUK, pos[i] = i / BUK, tocL[i] = 1, tocR[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 / BUK; for(int y : r[x]) if(bukR[y] > vr) buk_noviR(y, vr); } void noviL(int x, int vr){ //printf("novi x = %d sa vr = %d\n", x, vr); L[x] = vr; for(int y : v[x]) if(L[y] < vr && pos[y] == vr / BUK) noviL(y, vr); } void noviR(int x, int vr){ R[x] = vr; for(int y : r[x]) if(R[y] > vr && pos[y] == vr / BUK) noviR(y, vr); } void oznaci_nap(int x, int vr){ if(pos[x] == -1) { pos[x] = vr; } tocR[x] = 1; kad[x] = tme; for(int y : v[x]){ if(!tocR[y] || kad[y] == SAD) oznaci_nap(y, vr); R[x] = min(R[x], R[y]); } } void oznaci_naz(int x, int vr){ if(pos[x] == -1){ pos[x] = vr; } tocL[x] = 1; kad[x] = tme; for(int y : r[x]){ if(!tocL[y] || kad[y] == SAD) oznaci_naz(y, vr); L[x] = max(L[x], L[y]); } } void update(int a){ if(pos[a] != -1 && !tocR[a]){ SAD = -1; tme++; oznaci_nap(a, pos[a]); SAD = tme; tme++; oznaci_nap(a, pos[a]); } if(pos[a] != -1 && !tocL[a]) { SAD = -1; tme++; oznaci_naz(a, pos[a]); SAD = tme; tme++; oznaci_naz(a, pos[a]); } } int add_teleporter(int a, int b) { v[a].PB(b), r[b].PB(a); if(pos[a] != -1) pos[b] = pos[a]; if(pos[b] != -1) pos[a] = pos[b]; 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]; update(a); update(b); if(L[b] < L[a] && pos[b] == L[a] / BUK) noviL(b, L[a]); if(R[a] > R[b] && pos[a] == R[b] / BUK) noviR(a, R[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...