Submission #709442

#	Time	Username	Problem	Language	Result	Execution time	Memory
709442		doowey	Game (APIO22_game)	C++17	60 / 100	4045 ms	47896 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;
        for(auto x : T[v]){
            if(explore(v, x)) return 1;
        }
        for(auto x : R[v]){
            if(explore(x, v)) return 1;
        }
    }
    if(G[v].se < G[u].se){
        G[u].se = G[v].se;
        for(auto x : T[u]){
            if(explore(u, x)) return 1;
        }
        for(auto x : R[u]){
            if(explore(x, u)) 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: 0 / 40