Submission #838504

#	Time	Username	Problem	Language	Result	Execution time	Memory
838504		finn__	Game (APIO22_game)	C++17	30 / 100	92 ms	488 KiB

game

#include <bits/stdc++.h>
#include "game.h"
using namespace std;

constexpr size_t N = 1000;

int n, k;
vector<int> g[N], rg[N], postorder;
bitset<N> visited;

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

void dfs_postorder(int u)
{
    visited[u] = 1;
    for (int const &v : g[u])
        if (!visited[v])
            dfs_postorder(v);
    postorder.push_back(u);
}

bool find_scc(int u, int &scc_size)
{
    visited[u] = 1;
    ++scc_size;
    if (u < k && scc_size > 1)
        return 1;
    for (int const &v : rg[u])
        if (!visited[v])
        {
            if (u < k)
                return 1;
            if (find_scc(v, scc_size))
                return 1;
        }
    return 0;
}

int add_teleporter(int u, int v)
{
    if (u < k && u == v)
        return 1;
    g[u].push_back(v);
    rg[v].push_back(u);

    visited.reset();
    postorder.clear();
    for (int i = 0; i < n; ++i)
        if (!visited[i])
            dfs_postorder(i);
    visited.reset();
    reverse(postorder.begin(), postorder.end());
    for (int const &i : postorder)
        if (!visited[i])
        {
            int scc_size = 0;
            if (find_scc(i, scc_size))
                return 1;
        }
    return 0;
}

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