Submission #974308

#	Time	Username	Problem	Language	Result	Execution time	Memory
974308		Tuanlinh123	Game (APIO22_game)	C++17	0 / 100	6 ms	26968 KiB

game

#include "game.h"
#include<bits/stdc++.h>
#define ll int
#define pll pair<ll, ll>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define ld long double
#define sz(a) ((ll)(a).size())
using namespace std;

const ll maxn=300005;
ll n, k, a[20][maxn];
vector <ll> A[maxn], At[maxn];
bool ismid[20][maxn];

ll propagate(ll i, ll r, ll t)
{
    queue <ll> q; 
    if (a[i][r]+t==3) return 1;
    if (!a[i][r]) a[i][r]=t, q.push(r);
    while (sz(q))
    {
        ll u=q.front(); q.pop();
        for (ll v:(t==1?A[u]:At[u]))
        {
            if (a[i][v]+t==3) return 1;
            if (!a[i][v]) a[i][v]=t, q.push(v);
        }
    }
    return 0;
}

ll addedge(ll u, ll v)
{
    A[u].pb(v), At[v].pb(u);
    for (ll i=0, oku=3, okv=3; i<20 && oku==okv; i++)
    {
        if (a[i][u]==1) if (propagate(i, v, 1)) return 1;
        if ((a[i][v]==2 || ismid[i][v]) && oku) if (propagate(i, u, 2)) return 1;
        oku&=a[i][u], okv&=a[i][v];
    }
    return 0;
}

void init(int N, int K)
{
    n=N, k=K;
    function <void(ll, ll, ll)> init=[&](ll l, ll r, ll lay)
    {
        if (l>r) return;
        ll mid=(l+r)/2; a[lay][mid]=ismid[lay][mid]=1;
        init(l, mid-1, lay+1), init(mid+1, r, lay+1);
    }; init(0, k-1, 0);
    for (ll i=0; i+1<k; i++) addedge(i, i+1);
}
int add_teleporter(int u, int v) {return addedge(u, v);}

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