Submission #981703

#	Time	Username	Problem	Language	Result	Execution time	Memory
981703		crafticat	Game (APIO22_game)	C++17	30 / 100	4018 ms	5936 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);
    }
}

vector<bool> vis;
int dfs(int x) {
    vis[x] = true;
    int v = x < K ? x : inf;

    for (auto child : g[x]) {
        if (vis[child]) continue;
        v = min(v, dfs(child));
    }
    return v;
}
int dfs2(int x) {
    vis[x] = true;
    int v = x < K ? x : -1;

    for (auto child : gr[x]) {
        if (vis[child]) continue;
        v = max(v, dfs2(child));
    }
    return v;
}

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

    g[u].push_back(v);
    gr[v].push_back(u);
    vis.clear();
    vis.resize(g.size());
    int x = dfs(v);
    vis.clear();
    vis.resize(g.size());
    int y = dfs2(u);
    pos = x > y;

    return !pos;
}

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