Submission #709443

#	Time	Username	Problem	Language	Result	Execution time	Memory
709443		doowey	Game (APIO22_game)	C++17	100 / 100	1889 ms	109748 KiB

game

#include "game.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair

const int N = (int)3e5 + 10;

vector<int> T[N];
vector<int> R[N];

pii G[N];
pii layer[N];

void init(int n, int k) {
    for(int i = 1 ; i <= n; i ++ ){
        if(i <= k){
            G[i] = mp(i, i);
        }
        else{
            G[i] = mp(0, k + 1);
        }
        layer[i] = mp(0, k + 1);
    }
}

int explore(int u, int v){
    if(G[u].fi >= G[v].se){
        return 1;
    }
    if(G[u].fi > G[v].fi){
        G[v].fi = G[u].fi;
    }
    if(G[v].se < G[u].se){
        G[u].se = G[v].se;
    }
    if((layer[u].fi < layer[u].se) && (layer[u].fi + layer[u].se) / 2 >= G[u].se){
        layer[u].se = (layer[u].fi + layer[u].se) / 2;
        for(auto x : T[u]){
            if(explore(u, x)) return 1;
        }
        for(auto x : R[u]){
            if(explore(x, u)) return 1;
        }
    }
    else if((layer[u].fi < layer[u].se) && (layer[u].fi + layer[u].se) / 2 < G[u].fi){
        layer[u].fi = (layer[u].fi + layer[u].se) / 2 + 1;
        for(auto x : T[u]){
            if(explore(u, x)) return 1;
        }
        for(auto x : R[u]){
            if(explore(x, u)) return 1;
        }
    }
    else if((layer[v].fi < layer[v].se) && (layer[v].fi + layer[v].se) / 2 >= G[v].se){
        layer[v].se = (layer[v].fi + layer[v].se) / 2;
        for(auto x : T[v]){
            if(explore(v, x)) return 1;
        }
        for(auto x : R[v]){
            if(explore(x, v)) return 1;
        }
    }
    else if((layer[v].fi < layer[v].se) && (layer[v].fi + layer[v].se) / 2 < G[v].fi){
        layer[v].fi = (layer[v].fi + layer[v].se) / 2 + 1;
        for(auto x : T[v]){
            if(explore(v, x)) return 1;
        }
        for(auto x : R[v]){
            if(explore(x, v)) return 1;
        }
    }
    return 0;
}

int add_teleporter(int u, int v) {
    u ++ ;
    v ++ ;
    T[u].push_back(v);
    R[v].push_back(u);
    return explore(u, v);
}

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