제출 #822136

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

game

#include "game.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> adj[300005], radj[300005];
int l[300005], r[300005];
void init(int n, int k)
{
    for (int i=0; i<k; i++)
        l[i]=i, r[i]=i;
    for (int i=k; i<n; i++)
        l[i]=-1, r[i]=k+1;
}
int recur(int u, int v)
{
    if (l[u]>=r[v])
        return 1;
    int midu=(l[u]+r[u])/2, midv=(l[v]+r[v])/2;
    if (l[u]>midv)
    {
        l[v]=midv+1;
        midv=(l[v]+r[v])/2;
        if (l[u]<=midv)
        {
            for (int w:adj[v])
                if (recur(v, w))
                    return 1;
            for (int w:radj[v])
                if (w!=u && recur(w, v))
                    return 1;
        }
    }
    if (r[v]<=midu)
    {
        r[u]=midu;
        midu=(l[u]+r[u])/2;
        if (r[v]>midu)
        {
            for (int w:adj[u])
                if (w!=v && recur(u, w))
                    return 1;
            for (int w:radj[u])
                if (recur(w, u))
                    return 1;
        }
    }
    return 0;
}
int add_teleporter(int u, int v)
{
    adj[u].push_back(v), radj[v].push_back(u);
    return recur(u, v);
}

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