Submission #572718

#	Time	Username	Problem	Language	Result	Execution time	Memory
572718		baluteshih	Game (APIO22_game)	C++17	60 / 100	4067 ms	42644 KiB

game

#include "game.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define X first
#define Y second
#define SZ(a) ((int)a.size())
#define ALL(v) v.begin(), v.end()
#define pb push_back

const int MAXN = 300005;
vector<int> G[MAXN], rG[MAXN];
pii itv[MAXN];
int done, K;

void dfs(int u, int nw) {
    itv[u].Y = max(itv[u].Y, nw);
    if (itv[u].X <= itv[u].Y)
        done = 1;
    for (int i : G[u])
        if (itv[i].Y < nw)
            dfs(i, nw);
}

void rdfs(int u, int nw) {
    itv[u].X = min(itv[u].X, nw);
    if (itv[u].X <= itv[u].Y)
        done = 1;
    for (int i : rG[u])
        if (itv[i].X > nw)
            rdfs(i, nw);
}

void init(int n, int k) {
    K = k;
    for (int i = 0; i < n; ++i)
        G[i].clear(), rG[i].clear();
    for (int i = 0; i < k; ++i)
        itv[i] = pii(i, i);
    for (int i = k; i < n; ++i)
        itv[i] = pii(n, -1);
    done = 0;
}

int add_teleporter(int u, int v) {
    if (done) return 1;
    if (u < K && v < K) {
        if (u >= v)
            return done = 1;
        return 0;
    }
    if (u < K) {
        if (u <= itv[v].Y) return 0;
        dfs(v, u);
    }
    else if (v < K) {
        if (v >= itv[u].X) return 0;
        rdfs(u, v);
    }
    else {
        G[u].pb(v);
        rG[v].pb(u);
        if (itv[u].Y > itv[v].Y)
            dfs(v, itv[u].Y);
        if (itv[v].X < itv[u].X)
            rdfs(u, itv[v].X);
    }
    return done;
}

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