Submission #711232

#	Time	Username	Problem	Language	Result	Execution time	Memory
711232		Astrayt	Game (APIO22_game)	C++17	100 / 100	1575 ms	149068 KiB

game

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define maxn 300005
 
int N, K, L[maxn], R[maxn], fin = 0;
vector<int> adj[maxn], rev[maxn];
 
void init(int n, int k){
    N = n, K = k;
    for(int i = 0; i < K - 1; ++i) adj[i].pb(i + 1), rev[i + 1].pb(i);
    for(int i = 0; i < K; ++i) L[i] = R[i] = i;
    for(int i = K; i < n; ++i) L[i] = -1, R[i] = K;
}

void update(int u, int v){
    if(L[u] >= R[v]) {
        fin = 1;
        return;
    }   
    int midu = (L[u] + R[u]) >> 1, midv = (L[v] + R[v]) >> 1;
    if(L[u] > midv) {
        L[v] = midv + 1;
        for(auto x:adj[v]) update(v, x);
        for(auto x:rev[v]) update(x, v);
    }
    if(R[v] <= midu){
        R[u] = midu;
        for(auto x:adj[u]) update(u, x);
        for(auto x:rev[u]) update(x, u);
    }
}
 
int add_teleporter(int u, int v){
    if(u == v){
        if(u < K) return 1;
        return 0;
    }
    adj[u].pb(v);
    rev[v].pb(u);
    update(u, v);
    return fin;
}

• Subtask 1: 2 / 2
• Subtask 2: 10 / 10
• Subtask 3: 18 / 18
• Subtask 4: 30 / 30
• Subtask 5: 40 / 40