oj.uz

Submission #976368

# Submission time Handle Problem Language Result Execution time Memory
976368 2024-05-06T13:35:33 Z Unforgettablepl Game (APIO22_game) C++17
30 / 100
 4000 ms 10176 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long

vector<int> adj[300001];
int K,N;

void init(int32_t n, int32_t k) {
    N=n;K=k;
    for(int i=0;i<k-1;i++)adj[i].emplace_back(i+1);
}

vector<pair<bool,bool>> visited;
vector<int> ans;

int DFS(int x){
    if(visited[x].second)return 0;
    if(visited[x].first){
        if(x<K){ans.emplace_back(x);
        return x;}
        return 0;
    }
    visited[x].first=true;
    for(int&i:adj[x]){
        int temp = DFS(i);
        if(temp==0)continue;
        if(temp==-1)return -1;
        ans.emplace_back(x);
        if(x==temp)return -1;
        return temp;
    }
    visited[x].first=false;
    visited[x].second=true;
    return 0;
}


int32_t add_teleporter(int32_t u, int32_t v) {
    visited = vector<pair<bool,bool>>(N);
    adj[u].emplace_back(v);
    DFS(0);
    return min(1,(int32_t)ans.size());
}



//namespace {
//
//    int32_t read_int() {
//        int32_t x;
//        if (scanf("%d", &x) != 1) {
//            fprintf(stderr, "Error while reading input\n");
//            exit(1);
//        }
//        return x;
//    }
//
//}  // namespace
//
//int32_t main() {
//    int32_t N = read_int();
//    int32_t M = read_int();
//    int32_t K = read_int();
//    std::vector<int32_t> u(M), v(M);
//    for (int32_t i = 0; i < M; ++i) {
//        u[i] = read_int();
//        v[i] = read_int();
//    }
//
//    init(N, K);
//    int32_t i;
//    for (i = 0; i < M; ++i) {
//        int32_t answer = add_teleporter(u[i], v[i]);
//        if (answer != 0 && answer != 1) {
//            i = -1;
//            break;
//        } else if (answer == 1) {
//            break;
//        }
//    }
//    printf("%d\n", i);
//    return 0;
//}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7256 KB Output is correct
2 Correct 2 ms 7256 KB Output is correct
3 Correct 3 ms 7256 KB Output is correct
4 Correct 2 ms 7256 KB Output is correct
5 Correct 2 ms 7256 KB Output is correct
6 Correct 2 ms 7256 KB Output is correct
7 Correct 2 ms 7256 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7256 KB Output is correct
2 Correct 2 ms 7256 KB Output is correct
3 Correct 3 ms 7256 KB Output is correct
4 Correct 2 ms 7256 KB Output is correct
5 Correct 2 ms 7256 KB Output is correct
6 Correct 2 ms 7256 KB Output is correct
7 Correct 2 ms 7256 KB Output is correct
8 Correct 2 ms 7256 KB Output is correct
9 Correct 2 ms 7256 KB Output is correct
10 Correct 2 ms 7256 KB Output is correct
11 Correct 2 ms 7256 KB Output is correct
12 Correct 2 ms 7256 KB Output is correct
13 Correct 3 ms 7260 KB Output is correct
14 Correct 2 ms 7256 KB Output is correct
15 Correct 2 ms 7256 KB Output is correct
16 Correct 3 ms 7256 KB Output is correct
17 Correct 2 ms 7256 KB Output is correct
18 Correct 3 ms 7256 KB Output is correct
19 Correct 2 ms 7256 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7256 KB Output is correct
2 Correct 2 ms 7256 KB Output is correct
3 Correct 3 ms 7256 KB Output is correct
4 Correct 2 ms 7256 KB Output is correct
5 Correct 2 ms 7256 KB Output is correct
6 Correct 2 ms 7256 KB Output is correct
7 Correct 2 ms 7256 KB Output is correct
8 Correct 2 ms 7256 KB Output is correct
9 Correct 2 ms 7256 KB Output is correct
10 Correct 2 ms 7256 KB Output is correct
11 Correct 2 ms 7256 KB Output is correct
12 Correct 2 ms 7256 KB Output is correct
13 Correct 3 ms 7260 KB Output is correct
14 Correct 2 ms 7256 KB Output is correct
15 Correct 2 ms 7256 KB Output is correct
16 Correct 3 ms 7256 KB Output is correct
17 Correct 2 ms 7256 KB Output is correct
18 Correct 3 ms 7256 KB Output is correct
19 Correct 2 ms 7256 KB Output is correct
20 Correct 4 ms 7256 KB Output is correct
21 Correct 2 ms 7256 KB Output is correct
22 Correct 5 ms 7512 KB Output is correct
23 Correct 4 ms 7512 KB Output is correct
24 Correct 9 ms 7768 KB Output is correct
25 Correct 37 ms 8304 KB Output is correct
26 Correct 45 ms 8024 KB Output is correct
27 Correct 52 ms 7768 KB Output is correct
28 Correct 18 ms 7768 KB Output is correct
29 Correct 49 ms 8028 KB Output is correct

Subtask #4
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7256 KB Output is correct
2 Correct 2 ms 7256 KB Output is correct
3 Correct 3 ms 7256 KB Output is correct
4 Correct 2 ms 7256 KB Output is correct
5 Correct 2 ms 7256 KB Output is correct
6 Correct 2 ms 7256 KB Output is correct
7 Correct 2 ms 7256 KB Output is correct
8 Correct 2 ms 7256 KB Output is correct
9 Correct 2 ms 7256 KB Output is correct
10 Correct 2 ms 7256 KB Output is correct
11 Correct 2 ms 7256 KB Output is correct
12 Correct 2 ms 7256 KB Output is correct
13 Correct 3 ms 7260 KB Output is correct
14 Correct 2 ms 7256 KB Output is correct
15 Correct 2 ms 7256 KB Output is correct
16 Correct 3 ms 7256 KB Output is correct
17 Correct 2 ms 7256 KB Output is correct
18 Correct 3 ms 7256 KB Output is correct
19 Correct 2 ms 7256 KB Output is correct
20 Correct 4 ms 7256 KB Output is correct
21 Correct 2 ms 7256 KB Output is correct
22 Correct 5 ms 7512 KB Output is correct
23 Correct 4 ms 7512 KB Output is correct
24 Correct 9 ms 7768 KB Output is correct
25 Correct 37 ms 8304 KB Output is correct
26 Correct 45 ms 8024 KB Output is correct
27 Correct 52 ms 7768 KB Output is correct
28 Correct 18 ms 7768 KB Output is correct
29 Correct 49 ms 8028 KB Output is correct
30 Correct 618 ms 8308 KB Output is correct
31 Correct 207 ms 7964 KB Output is correct
32 Correct 629 ms 9264 KB Output is correct
33 Correct 607 ms 8608 KB Output is correct
34 Correct 1670 ms 10176 KB Output is correct
35 Execution timed out 4098 ms 8472 KB Time limit exceeded
36 Halted 0 ms 0 KB -

Subtask #5
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7256 KB Output is correct
2 Correct 2 ms 7256 KB Output is correct
3 Correct 3 ms 7256 KB Output is correct
4 Correct 2 ms 7256 KB Output is correct
5 Correct 2 ms 7256 KB Output is correct
6 Correct 2 ms 7256 KB Output is correct
7 Correct 2 ms 7256 KB Output is correct
8 Correct 2 ms 7256 KB Output is correct
9 Correct 2 ms 7256 KB Output is correct
10 Correct 2 ms 7256 KB Output is correct
11 Correct 2 ms 7256 KB Output is correct
12 Correct 2 ms 7256 KB Output is correct
13 Correct 3 ms 7260 KB Output is correct
14 Correct 2 ms 7256 KB Output is correct
15 Correct 2 ms 7256 KB Output is correct
16 Correct 3 ms 7256 KB Output is correct
17 Correct 2 ms 7256 KB Output is correct
18 Correct 3 ms 7256 KB Output is correct
19 Correct 2 ms 7256 KB Output is correct
20 Correct 4 ms 7256 KB Output is correct
21 Correct 2 ms 7256 KB Output is correct
22 Correct 5 ms 7512 KB Output is correct
23 Correct 4 ms 7512 KB Output is correct
24 Correct 9 ms 7768 KB Output is correct
25 Correct 37 ms 8304 KB Output is correct
26 Correct 45 ms 8024 KB Output is correct
27 Correct 52 ms 7768 KB Output is correct
28 Correct 18 ms 7768 KB Output is correct
29 Correct 49 ms 8028 KB Output is correct
30 Correct 618 ms 8308 KB Output is correct
31 Correct 207 ms 7964 KB Output is correct
32 Correct 629 ms 9264 KB Output is correct
33 Correct 607 ms 8608 KB Output is correct
34 Correct 1670 ms 10176 KB Output is correct
35 Execution timed out 4098 ms 8472 KB Time limit exceeded
36 Halted 0 ms 0 KB -