oj.uz

Submission #613599

# Submission time Handle Problem Language Result Execution time Memory
613599 2022-07-30T07:19:56 Z Aldas25 Game (APIO22_game) C++17
12 / 100
 4000 ms 20420 KB 
#include "game.h"

#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define f first
#define s second
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define REP(n) FOR(O, 1, (n))
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef vector<pii> vii;

const int MAXN = 500100;

vi adj[MAXN];
int n, k;
bool vis[MAXN];
bool still[MAXN];
bool cycle = false;
vi was;

void dfs (int v) {
    if (cycle) return;
    was.pb(v);
    vis[v] = true;
    still[v] = true;
    for (int u : adj[v]) {
        if (vis[u]) {
            if (still[u] && u < k) {
                cycle = true;
                return;
            }
        } else dfs(u);
    }

    still[v] = false;
}

void init(int N, int K) {
    n = N;
    k = K;
    FOR(i, 0, k-2) adj[i].pb(i+1);
}

int add_teleporter(int u, int v) {
    adj[u].pb(v);
    cycle = false;
    //FOR(i, 0,n-1) vis[i] = false;
    dfs(0);
    for (int x : was) vis[x] = false;
    return cycle;
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11984 KB Output is correct
2 Correct 6 ms 11984 KB Output is correct
3 Correct 19 ms 12296 KB Output is correct
4 Correct 8 ms 12088 KB Output is correct
5 Correct 18 ms 12240 KB Output is correct
6 Correct 19 ms 12240 KB Output is correct
7 Correct 19 ms 12240 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11984 KB Output is correct
2 Correct 6 ms 11984 KB Output is correct
3 Correct 19 ms 12296 KB Output is correct
4 Correct 8 ms 12088 KB Output is correct
5 Correct 18 ms 12240 KB Output is correct
6 Correct 19 ms 12240 KB Output is correct
7 Correct 19 ms 12240 KB Output is correct
8 Correct 6 ms 11984 KB Output is correct
9 Correct 6 ms 11984 KB Output is correct
10 Correct 6 ms 11984 KB Output is correct
11 Correct 6 ms 11960 KB Output is correct
12 Correct 6 ms 11984 KB Output is correct
13 Correct 7 ms 11984 KB Output is correct
14 Correct 8 ms 12112 KB Output is correct
15 Correct 11 ms 12112 KB Output is correct
16 Correct 10 ms 12116 KB Output is correct
17 Correct 14 ms 12240 KB Output is correct
18 Correct 9 ms 12164 KB Output is correct
19 Correct 9 ms 12096 KB Output is correct

Subtask #3
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11984 KB Output is correct
2 Correct 6 ms 11984 KB Output is correct
3 Correct 19 ms 12296 KB Output is correct
4 Correct 8 ms 12088 KB Output is correct
5 Correct 18 ms 12240 KB Output is correct
6 Correct 19 ms 12240 KB Output is correct
7 Correct 19 ms 12240 KB Output is correct
8 Correct 6 ms 11984 KB Output is correct
9 Correct 6 ms 11984 KB Output is correct
10 Correct 6 ms 11984 KB Output is correct
11 Correct 6 ms 11960 KB Output is correct
12 Correct 6 ms 11984 KB Output is correct
13 Correct 7 ms 11984 KB Output is correct
14 Correct 8 ms 12112 KB Output is correct
15 Correct 11 ms 12112 KB Output is correct
16 Correct 10 ms 12116 KB Output is correct
17 Correct 14 ms 12240 KB Output is correct
18 Correct 9 ms 12164 KB Output is correct
19 Correct 9 ms 12096 KB Output is correct
20 Correct 25 ms 12368 KB Output is correct
21 Correct 8 ms 12112 KB Output is correct
22 Correct 103 ms 12632 KB Output is correct
23 Correct 18 ms 12112 KB Output is correct
24 Correct 831 ms 16308 KB Output is correct
25 Execution timed out 4096 ms 20420 KB Time limit exceeded
26 Halted 0 ms 0 KB -

Subtask #4
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11984 KB Output is correct
2 Correct 6 ms 11984 KB Output is correct
3 Correct 19 ms 12296 KB Output is correct
4 Correct 8 ms 12088 KB Output is correct
5 Correct 18 ms 12240 KB Output is correct
6 Correct 19 ms 12240 KB Output is correct
7 Correct 19 ms 12240 KB Output is correct
8 Correct 6 ms 11984 KB Output is correct
9 Correct 6 ms 11984 KB Output is correct
10 Correct 6 ms 11984 KB Output is correct
11 Correct 6 ms 11960 KB Output is correct
12 Correct 6 ms 11984 KB Output is correct
13 Correct 7 ms 11984 KB Output is correct
14 Correct 8 ms 12112 KB Output is correct
15 Correct 11 ms 12112 KB Output is correct
16 Correct 10 ms 12116 KB Output is correct
17 Correct 14 ms 12240 KB Output is correct
18 Correct 9 ms 12164 KB Output is correct
19 Correct 9 ms 12096 KB Output is correct
20 Correct 25 ms 12368 KB Output is correct
21 Correct 8 ms 12112 KB Output is correct
22 Correct 103 ms 12632 KB Output is correct
23 Correct 18 ms 12112 KB Output is correct
24 Correct 831 ms 16308 KB Output is correct
25 Execution timed out 4096 ms 20420 KB Time limit exceeded
26 Halted 0 ms 0 KB -

Subtask #5
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11984 KB Output is correct
2 Correct 6 ms 11984 KB Output is correct
3 Correct 19 ms 12296 KB Output is correct
4 Correct 8 ms 12088 KB Output is correct
5 Correct 18 ms 12240 KB Output is correct
6 Correct 19 ms 12240 KB Output is correct
7 Correct 19 ms 12240 KB Output is correct
8 Correct 6 ms 11984 KB Output is correct
9 Correct 6 ms 11984 KB Output is correct
10 Correct 6 ms 11984 KB Output is correct
11 Correct 6 ms 11960 KB Output is correct
12 Correct 6 ms 11984 KB Output is correct
13 Correct 7 ms 11984 KB Output is correct
14 Correct 8 ms 12112 KB Output is correct
15 Correct 11 ms 12112 KB Output is correct
16 Correct 10 ms 12116 KB Output is correct
17 Correct 14 ms 12240 KB Output is correct
18 Correct 9 ms 12164 KB Output is correct
19 Correct 9 ms 12096 KB Output is correct
20 Correct 25 ms 12368 KB Output is correct
21 Correct 8 ms 12112 KB Output is correct
22 Correct 103 ms 12632 KB Output is correct
23 Correct 18 ms 12112 KB Output is correct
24 Correct 831 ms 16308 KB Output is correct
25 Execution timed out 4096 ms 20420 KB Time limit exceeded
26 Halted 0 ms 0 KB -