oj.uz

Submission #974291

# Submission time Handle Problem Language Result Execution time Memory
974291 2024-05-03T07:34:14 Z Tuanlinh123 Game (APIO22_game) C++17
0 / 100
 4 ms 23000 KB 
#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 u, ll t)
{
    queue <ll> q; 
    if (a[i][u]+t==3) return 1;
    if (!a[i][u]) a[i][u]=t, q.push(u);
    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; i<20; i++)
    {
        if (a[i][u]==1) if (propagate(i, v, 1)) return 1;
        if (a[i][v]==2 || ismid[i][v]) if (propagate(i, u, 2)) return 1;
    }
    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.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16728 KB Output is correct
2 Incorrect 4 ms 23000 KB Wrong Answer[1]
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16728 KB Output is correct
2 Incorrect 4 ms 23000 KB Wrong Answer[1]
3 Halted 0 ms 0 KB -

Subtask #3
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16728 KB Output is correct
2 Incorrect 4 ms 23000 KB Wrong Answer[1]
3 Halted 0 ms 0 KB -

Subtask #4
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16728 KB Output is correct
2 Incorrect 4 ms 23000 KB Wrong Answer[1]
3 Halted 0 ms 0 KB -

Subtask #5
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16728 KB Output is correct
2 Incorrect 4 ms 23000 KB Wrong Answer[1]
3 Halted 0 ms 0 KB -