Submission #602279

#TimeUsernameProblemLanguageResultExecution timeMemory
602279patrikpavic2Game (APIO22_game)C++17
2 / 100
15 ms23832 KiB
#include "game.h" #include <vector> #include <cstdio> #define PB push_back using namespace std; const int N = 5e5 + 500; const int BUK = 1; int n, k, ans; vector < int > v[N], r[N]; int L[N], R[N], bukL[N], bukR[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] = 0, bukR[i] = k - 1; for(int i = 0;i < k;i++) L[i] = i, R[i] = i, bukL[i] = i / BUK, bukR[i] = i / BUK; } void buk_noviL(int x, int vr){ bukL[x] = vr / BUK; for(int y : v[x]) if(bukL[y] < vr / BUK) 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) 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 noviR(int x, int vr){ R[x] = vr; for(int y : r[x]) if(R[y] > vr && bukL[y] >= vr / BUK) noviR(y, vr); } 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, L[a]); if(bukR[a] > bukR[b]) buk_noviR(a, R[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]); 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...