Submission #974873

#TimeUsernameProblemLanguageResultExecution timeMemory
974873Tuanlinh123Game (APIO22_game)C++17
100 / 100
1237 ms64188 KiB
#include "game.h" #include<bits/stdc++.h> #define ll int #define pll pair<ll, ll> #define pb push_back #define mp make_pair #define fi first #define se second #define ld long double #define sz(a) ((ll)(a).size()) using namespace std; const ll maxn=300005; ll n, k, ok, l[maxn], r[maxn], layer[maxn]; vector <ll> A[maxn], At[maxn]; void propagate(ll u) { if (ok) return; if (r[u]<=l[u]) return ok=1, void(); ll j=__lg(l[u]^r[u]); if (layer[u]>j) layer[u]=j; else return; for (ll v:A[u]) l[v]=max(l[v], l[u]), propagate(v); for (ll v:At[u]) r[v]=min(r[v], r[u]), propagate(v); } ll addedge(ll u, ll v) { A[u].pb(v), At[v].pb(u); l[v]=max(l[v], max(l[u], u<k?u:-1)), propagate(v); r[u]=min(r[u], min(r[v], v<k?v:k)), propagate(u); return ok; } void init(int N, int K) { n=N, k=K; for (ll i=0; i<k; i++) l[i]=i, r[i]=i+1; for (ll i=k; i<n; i++) l[i]=-1, r[i]=k; for (ll i=0; i<n; i++) layer[i]=__lg(l[i]^r[i]); } int add_teleporter(int u, int v) {return addedge(u, v);}
#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...