Submission #1177383

#	Time	Username	Problem	Language	Result	Execution time	Memory
1177383		anmattroi	Game (APIO22_game)	C++17	0 / 100	4 ms	7488 KiB

game

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

using namespace std;

int N, K, num[maxn], low[maxn], id = 0, slt, sz[maxn], lt[maxn], cl[maxn], degenerate = 0;
vector<int> adj[maxn], Stack;

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

void dfs(int u) {
    cl[u] = 1;
    num[u] = low[u] = ++id;
    Stack.emplace_back(u);
    for (int v : adj[u])
    if (cl[v] == 0) {
        dfs(v);
        low[u] = min(low[u], low[v]);
    } else if (cl[v] == 1) low[u] = min(low[u], num[v]);

    if (num[u] == low[u]) {
        int v;
        sz[++slt] = 0;
        do {
            v = Stack.back();
            cl[v] = 2;
            lt[v] = slt;
            ++sz[slt];
            Stack.pop_back();
        } while (v != u);
    }
}

int add_teleporter(int u, int v) {
    if (degenerate) return 1;
    if (u == v && u < K) return degenerate = 1;

    adj[u].emplace_back(v);
    for (int i = 0; i < N; i++) cl[i] = 0;
    id = slt = 0;

    for (int i = 0; i < N; i++)
        if (!cl[i]) dfs(i);

    for (int i = 0; i < K; i++) if (sz[lt[i]] > 1) return 1;
    return 0;
}

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