Submission #822178

#	Time	Username	Problem	Language	Result	Execution time	Memory
822178		Hanksburger	Game (APIO22_game)	C++17	100 / 100	1489 ms	83316 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+1, r[i]=i+1;
    for (int i=k; i<n; i++)
        l[i]=0, r[i]=k+2;
}
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;
    while (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;
    }
    while (r[v]<=midu)
    {
        r[u]=midu;
        midu=(l[u]+r[u])/2;
        if (r[v]>midu)
            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: 10 / 10
• Subtask 3: 18 / 18
• Subtask 4: 30 / 30
• Subtask 5: 40 / 40