Submission #982493

#	Time	Username	Problem	Language	Result	Execution time	Memory
982493		sleepntsheep	Game (APIO22_game)	C++17	60 / 100	4080 ms	28584 KiB

game

#include "game.h"
#include <string>
#include <algorithm>

#define N 300000

std::basic_string<int> g[N], gt[N];
int n, k, from[N], to[N], cyclic;
/* igo >= goi */

void init(int n_, int k_) {
    n = n_, k = k_;
    for (int i = 0; i < k; ++i)
        to[i] = i, from[i] = i + 1;
    for (int i = k; i < n; ++i)
        from[i] = k, to[i] = -1;
}

void dfs1(int u, int xx) {
    if (from[u] <= xx)
        return;
    from[u] = xx;
    if (to[u] < k && from[u] <= to[u])
        cyclic = 1;
    for (auto v : gt[u])
        dfs1(v, xx);
}

void dfs2(int u, int xx) {
    if (to[u] >= xx)
        return;
    to[u] = xx;
    if (to[u] < k && from[u] <= to[u])
        cyclic = 1;
    for (auto v : g[u])
        dfs2(v, xx);
}

#include<stdio.h>
int add_teleporter(int u, int v) {
    g[u].push_back(v);
    gt[v].push_back(u);
    dfs1(u, std::min(v, from[v]));
    dfs2(v, to[u]);
    return cyclic;
}

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