제출 #981699

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
981699		crafticat	게임 (APIO22_game)	C++17	0 / 100	1 ms	344 KiB

game

#include <bits/stdc++.h>

using namespace std;

vector<vector<int>> g;
vector<vector<int>> gr;
constexpr int inf = 1e9;
int K = 0;
vector<int> toMin, fromMax;
bool pos = true;

void init(int n, int k) {
    g.resize(n + 1);
    gr.resize(n + 1);
    toMin.resize(n + 1,inf);
    fromMax.resize(n + 1,-1);
    K = k;

    for (int i = 0; i < k; ++i) {
        toMin[i] = i;
        fromMax[i] = i;
    }
    for (int i = 0; i < k - 1; ++i) {
        g[i].push_back(i + 1);
        gr[i + 1].push_back(i);
    }
}

// U -> V
bool push(int x) {
    if (fromMax[x] >= toMin[x] && x >= K)
        return true;
    for (auto par : g[x]) {
        if (toMin[par] > toMin[x]) {
            toMin[par] = toMin[x];
            if (push(par)) return true;
        }
    }
    return false;
}
bool push2(int x) {
    if (fromMax[x] >= toMin[x] && x >= K)
        return true;
    for (auto par : gr[x]) {
        if (fromMax[par] < fromMax[x]) {
            fromMax[par] = fromMax[x];
            if (push2(par)) return true;
        }
    }
    return false;
}

int add_teleporter(int u, int v) {
    if (!pos) return 1;

    if (u == v && v < K) {
        pos = false;
        return 1;
    }

    toMin[u] = min(toMin[v],toMin[u]);
    if (push(u)) pos = false;
    fromMax[v] = max(fromMax[v], fromMax[u]);
    if (push2(v)) pos = false;
    g[u].push_back(v);
    g[v].push_back(u);
    gr[v].push_back(u);
    gr[u].push_back(v);
    return !pos;
}

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