Submission #983832

#	Time	Username	Problem	Language	Result	Execution time	Memory
983832		vjudge1	Game (APIO22_game)	C++17	30 / 100	4086 ms	19188 KiB

game

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

using namespace std;

const int N = 300300;

int n, k;

vector<int> g[N];
vector<int> rg[N];

int cmp[N];
int tin[N], tout[N], T = 0;
bool vis[N];

void precalc(int s) {
    vis[s] = true;
    tin[s] = T++;
    for (int to : g[s]) if (!vis[to]) {
        precalc(to);
    }
    tout[s] = T++;
}

void dfs(int s, int c) {
    vis[s] = true;
    cmp[s] = c;
    for (int to : rg[s]) if (!vis[to]) {
        dfs(to, c);
    }
}

void init(int N, int K) {
    n = N, k = K;
    for (int i = 0; i < k - 1; i++) {
        g[i].push_back(i + 1);
        rg[i + 1].push_back(i);
    }
}

int add_teleporter(int u, int v) {
    if (u == v && u < k) return 1;
    T = 0;
    for (int i = 0; i < n; i++) {
        cmp[i] = 0;
        tin[i] = tout[i] = 0;
        vis[i] = false;
    }
    g[u].push_back(v);
    rg[v].push_back(u);

    for (int i = 0; i < n; i++) {
        if (vis[i]) continue;
        precalc(i);
    }
    vector<int> ord(n);
    iota(ord.begin(), ord.end(), 0);
    sort(ord.begin(), ord.end(), [](int x, int y) {
        return tout[x] > tout[y];
    });

    for (int i = 0; i < n; i++) vis[i] = false;

    int cnt = 1;
    for (int c : ord) {
        if (vis[c]) continue;
        dfs(c, cnt++);
    }
    int sz[cnt] = {};

    for (int i = 0; i < n; i++) {
        sz[cmp[i]]++;
    }
    for (int i = 0; i < k; i++) {
        if (sz[cmp[i]] > 1) {
            return 1;
        }
    }

    return 0;
}

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