oj.uz

Submission #572717

# Submission time Handle Problem Language Result Execution time Memory
572717 2022-06-05T06:57:52 Z baluteshih Game (APIO22_game) C++17
0 / 100
 8 ms 14288 KB 
#include "game.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define X first
#define Y second
#define SZ(a) ((int)a.size())
#define ALL(v) v.begin(), v.end()
#define pb push_back

const int MAXN = 300005;
vector<int> G[MAXN], rG[MAXN];
pii itv[MAXN];
int done, K;

void dfs(int u, int nw) {
    itv[u].Y = max(itv[u].Y, nw);
    if (itv[u].X <= itv[u].Y)
        done = 1;
    for (int i : G[u])
        if (itv[i].Y < nw)
            dfs(i, nw);
}

void rdfs(int u, int nw) {
    itv[u].X = min(itv[u].X, nw);
    if (itv[u].X <= itv[u].Y)
        done = 1;
    for (int i : rG[u])
        if (itv[i].X > nw)
            rdfs(i, nw);
}

void init(int n, int k) {
    K = k;
    for (int i = 0; i < n; ++i)
        G[i].clear(), rG[i].clear();
    for (int i = 0; i < k; ++i)
        itv[i] = pii(i, i);
    for (int i = k; i < n; ++i)
        itv[i] = pii(n, -1);
    done = 0;
}

int add_teleporter(int u, int v) {
    if (done) return 1;
    if (u < K && v < K) {
        if (u > v)
            return done = 1;
        return 0;
    }
    if (u < K) {
        if (u <= itv[v].Y) return 0;
        dfs(v, u);
    }
    else if (v < K) {
        if (v >= itv[u].X) return 0;
        rdfs(u, v);
    }
    else {
        G[u].pb(v);
        rG[v].pb(u);
        if (itv[u].Y > itv[v].Y)
            dfs(v, itv[u].Y);
        if (itv[v].X < itv[u].X)
            rdfs(u, itv[v].X);
    }
    return done;
}

Subtask #1
0.0 / 2.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 14288 KB Wrong Answer[1]
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 14288 KB Wrong Answer[1]
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 14288 KB Wrong Answer[1]
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 14288 KB Wrong Answer[1]
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 14288 KB Wrong Answer[1]
2 Halted 0 ms 0 KB -