제출 #838688

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
838688		finn__	게임 (APIO22_game)	C++17	2 / 100	7 ms	14432 KiB

game

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

constexpr size_t N = 300000;

size_t n, k, l[N], r[N];
vector<size_t> in[N], out[N];

bool update(size_t u, bool direction)
{
    if (!direction)
    {
        r[u] = (l[u] + r[u]) / 2;
        if (l[u] >= r[u])
            return 1;
        for (auto const &v : in[u])
            if (r[u] <= (l[v] + r[v]) / 2 && update(v, 0))
                return 1;
    }
    else
    {
        l[u] = (l[u] + r[u]) / 2 + 1;
        if (l[u] >= r[u])
            return 1;
        for (auto const &v : out[u])
            if (l[u] >= (l[v] + r[v]) / 2 && update(v, 1))
                return 1;
    }
    return 0;
}

void init(int n_, int k_)
{
    n = n_, k = k_;
    for (size_t i = 0; i < k; ++i)
        l[i] = i + 1, r[i] = i + 2;
    for (size_t i = k; i < n; ++i)
        l[i] = 0, r[i] = k + 1;
}

int add_teleporter(int u, int v)
{
    if (l[u] >= (l[v] + r[v]) / 2)
        if (update(v, 1))
            return 1;
    if (r[v] <= (l[u] + r[u]) / 2)
        if (update(u, 0))
            return 1;
    out[u].push_back(v);
    in[v].push_back(u);
    return 0;
}

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