oj.uz

Submission #622988

# Submission time Handle Problem Language Result Execution time Memory
622988 2022-08-04T23:32:48 Z Lobo Game (APIO22_game) C++17
100 / 100
 2792 ms 252152 KB 
#include "game.h"
#include<iostream>
#include<vector>
using namespace std;

#define pb push_back

const int maxn = 3e5+10;

int n, k, dir[maxn][30];
vector<int> g[maxn], gt[maxn];
int ans = 0;

/*
0 -> fora desse nível
1 -> chega em mid 
2 -> mid chega em
*/

void call(int a);
void att(int l, int r, int a, int b, int lv);
void call(int a) {
    for(auto b : g[a]) {
        att(0,k-1,a,b,0);
    }
    for(auto b : gt[a]) {
        att(0,k-1,b,a,0);
    }
}
void att(int l, int r, int a, int b, int lv) {
    if(l > r) return;
    int mid = (l+r)/2;
    if(a == mid) {
        if(dir[b][lv] == 0) {
            dir[b][lv] = 2; //mid chega no b
            call(b); //b muda
        }
        else if(dir[b][lv] == 1) {
            ans = 1; // b chega em mid e mid chega em b

        }
        return;
    }
    if(b == mid) {
        if(dir[a][lv] == 0) {
            dir[a][lv] = 1; //a chega em mid
            call(a); //a muda
        }
        else if(dir[a][lv] == 2) {
            ans = 1; // mid chega em a e a chega em mid
        }
        return;
    }

    if(dir[a][lv] == 0 && dir[b][lv] == 1) {
        //b chega em mid, a chega em b -> a chega em mid
        dir[a][lv] = 1;
        call(a); //a mudou
        att(l,mid-1,a,b,lv+1); //os dois tão no L
        return;
    }
    if(dir[a][lv] == 2 && dir[b][lv] == 0) {
        //mid chega em a, a chega em b -> mid chega em b
        dir[b][lv] = 2;
        call(b); //b mudou
        att(mid+1,r,a,b,lv+1); //os dois tão no R
        return;
    }
    if(dir[a][lv] == 2 && dir[b][lv] == 1) {
        //mid chega em a, a chega em b, b chega em mid -> mid chega em mid
        ans = 1;
        return;
    }
    if(dir[a][lv] == 1 && dir[b][lv] == 1) {
        att(l,mid-1,a,b,lv+1); //os dois tão no L | BRUTE ASSIM FICA LOG²
        return;
    }
    if(dir[a][lv] == 2 && dir[b][lv] == 2) {
        att(mid+1,r,a,b,lv+1);
        return;
    }

}

void build(int l, int r, int lv) {
    if(l > r) return;
    int mid = (l+r)/2;

    for(int i = l; i < mid; i++) {
        dir[i][lv] = 1;
    }
    for(int i = mid+1; i <= r; i++) {
        dir[i][lv] = 2;
    }

    build(l,mid-1,lv+1);
    build(mid+1,r,lv+1);
}

void init(int N, int K) {
    n = N;
    k = K;
    build(0,k-1,0);
    
}

int add_teleporter(int u, int v) {
    g[u].pb(v);
    gt[v].pb(u);
    if(u == v && u < k) return 1;
    att(0,k-1,u,v,0);
    return ans;
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14400 KB Output is correct
2 Correct 7 ms 14288 KB Output is correct
3 Correct 7 ms 14416 KB Output is correct
4 Correct 7 ms 14288 KB Output is correct
5 Correct 8 ms 14416 KB Output is correct
6 Correct 8 ms 14416 KB Output is correct
7 Correct 9 ms 14288 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14400 KB Output is correct
2 Correct 7 ms 14288 KB Output is correct
3 Correct 7 ms 14416 KB Output is correct
4 Correct 7 ms 14288 KB Output is correct
5 Correct 8 ms 14416 KB Output is correct
6 Correct 8 ms 14416 KB Output is correct
7 Correct 9 ms 14288 KB Output is correct
8 Correct 7 ms 14288 KB Output is correct
9 Correct 8 ms 14388 KB Output is correct
10 Correct 8 ms 14288 KB Output is correct
11 Correct 7 ms 14288 KB Output is correct
12 Correct 7 ms 14416 KB Output is correct
13 Correct 7 ms 14288 KB Output is correct
14 Correct 7 ms 14416 KB Output is correct
15 Correct 8 ms 14404 KB Output is correct
16 Correct 8 ms 14416 KB Output is correct
17 Correct 8 ms 14416 KB Output is correct
18 Correct 8 ms 14416 KB Output is correct
19 Correct 7 ms 14416 KB Output is correct
20 Correct 8 ms 14544 KB Output is correct
21 Correct 7 ms 14416 KB Output is correct
22 Correct 9 ms 14800 KB Output is correct
23 Correct 8 ms 14544 KB Output is correct
24 Correct 8 ms 14672 KB Output is correct
25 Correct 10 ms 14672 KB Output is correct
26 Correct 10 ms 14544 KB Output is correct
27 Correct 10 ms 14504 KB Output is correct
28 Correct 10 ms 14800 KB Output is correct
29 Correct 10 ms 14832 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14400 KB Output is correct
2 Correct 7 ms 14288 KB Output is correct
3 Correct 7 ms 14416 KB Output is correct
4 Correct 7 ms 14288 KB Output is correct
5 Correct 8 ms 14416 KB Output is correct
6 Correct 8 ms 14416 KB Output is correct
7 Correct 9 ms 14288 KB Output is correct
8 Correct 7 ms 14288 KB Output is correct
9 Correct 8 ms 14388 KB Output is correct
10 Correct 8 ms 14288 KB Output is correct
11 Correct 7 ms 14288 KB Output is correct
12 Correct 7 ms 14416 KB Output is correct
13 Correct 7 ms 14288 KB Output is correct
14 Correct 7 ms 14416 KB Output is correct
15 Correct 8 ms 14404 KB Output is correct
16 Correct 8 ms 14416 KB Output is correct
17 Correct 8 ms 14416 KB Output is correct
18 Correct 8 ms 14416 KB Output is correct
19 Correct 7 ms 14416 KB Output is correct
20 Correct 8 ms 14544 KB Output is correct
21 Correct 7 ms 14416 KB Output is correct
22 Correct 9 ms 14800 KB Output is correct
23 Correct 8 ms 14544 KB Output is correct
24 Correct 8 ms 14672 KB Output is correct
25 Correct 10 ms 14672 KB Output is correct
26 Correct 10 ms 14544 KB Output is correct
27 Correct 10 ms 14504 KB Output is correct
28 Correct 10 ms 14800 KB Output is correct
29 Correct 10 ms 14832 KB Output is correct
30 Correct 23 ms 18136 KB Output is correct
31 Correct 16 ms 15696 KB Output is correct
32 Correct 45 ms 33628 KB Output is correct
33 Correct 30 ms 19864 KB Output is correct
34 Correct 94 ms 47020 KB Output is correct
35 Correct 74 ms 22828 KB Output is correct
36 Correct 56 ms 19920 KB Output is correct
37 Correct 63 ms 19748 KB Output is correct
38 Correct 41 ms 19492 KB Output is correct
39 Correct 54 ms 19668 KB Output is correct
40 Correct 85 ms 52520 KB Output is correct
41 Correct 70 ms 24360 KB Output is correct
42 Correct 57 ms 24744 KB Output is correct
43 Correct 78 ms 22084 KB Output is correct
44 Correct 83 ms 27040 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14400 KB Output is correct
2 Correct 7 ms 14288 KB Output is correct
3 Correct 7 ms 14416 KB Output is correct
4 Correct 7 ms 14288 KB Output is correct
5 Correct 8 ms 14416 KB Output is correct
6 Correct 8 ms 14416 KB Output is correct
7 Correct 9 ms 14288 KB Output is correct
8 Correct 7 ms 14288 KB Output is correct
9 Correct 8 ms 14388 KB Output is correct
10 Correct 8 ms 14288 KB Output is correct
11 Correct 7 ms 14288 KB Output is correct
12 Correct 7 ms 14416 KB Output is correct
13 Correct 7 ms 14288 KB Output is correct
14 Correct 7 ms 14416 KB Output is correct
15 Correct 8 ms 14404 KB Output is correct
16 Correct 8 ms 14416 KB Output is correct
17 Correct 8 ms 14416 KB Output is correct
18 Correct 8 ms 14416 KB Output is correct
19 Correct 7 ms 14416 KB Output is correct
20 Correct 8 ms 14544 KB Output is correct
21 Correct 7 ms 14416 KB Output is correct
22 Correct 9 ms 14800 KB Output is correct
23 Correct 8 ms 14544 KB Output is correct
24 Correct 8 ms 14672 KB Output is correct
25 Correct 10 ms 14672 KB Output is correct
26 Correct 10 ms 14544 KB Output is correct
27 Correct 10 ms 14504 KB Output is correct
28 Correct 10 ms 14800 KB Output is correct
29 Correct 10 ms 14832 KB Output is correct
30 Correct 23 ms 18136 KB Output is correct
31 Correct 16 ms 15696 KB Output is correct
32 Correct 45 ms 33628 KB Output is correct
33 Correct 30 ms 19864 KB Output is correct
34 Correct 94 ms 47020 KB Output is correct
35 Correct 74 ms 22828 KB Output is correct
36 Correct 56 ms 19920 KB Output is correct
37 Correct 63 ms 19748 KB Output is correct
38 Correct 41 ms 19492 KB Output is correct
39 Correct 54 ms 19668 KB Output is correct
40 Correct 85 ms 52520 KB Output is correct
41 Correct 70 ms 24360 KB Output is correct
42 Correct 57 ms 24744 KB Output is correct
43 Correct 78 ms 22084 KB Output is correct
44 Correct 83 ms 27040 KB Output is correct
45 Correct 241 ms 30760 KB Output is correct
46 Correct 15 ms 14996 KB Output is correct
47 Correct 15 ms 15136 KB Output is correct
48 Correct 365 ms 88428 KB Output is correct
49 Correct 281 ms 60196 KB Output is correct
50 Correct 1286 ms 252152 KB Output is correct
51 Correct 1656 ms 114888 KB Output is correct
52 Correct 714 ms 68516 KB Output is correct
53 Correct 1186 ms 69036 KB Output is correct
54 Correct 1500 ms 68944 KB Output is correct
55 Correct 1764 ms 71200 KB Output is correct
56 Correct 2202 ms 69652 KB Output is correct
57 Correct 620 ms 62612 KB Output is correct
58 Correct 691 ms 62636 KB Output is correct
59 Correct 698 ms 62636 KB Output is correct
60 Correct 841 ms 62644 KB Output is correct
61 Correct 1321 ms 62360 KB Output is correct
62 Correct 888 ms 86424 KB Output is correct
63 Correct 763 ms 94716 KB Output is correct
64 Correct 2008 ms 171592 KB Output is correct
65 Correct 822 ms 76104 KB Output is correct
66 Correct 814 ms 72024 KB Output is correct
67 Correct 1395 ms 126792 KB Output is correct
68 Correct 201 ms 51576 KB Output is correct
69 Correct 58 ms 27968 KB Output is correct
70 Correct 1341 ms 115040 KB Output is correct
71 Correct 355 ms 62240 KB Output is correct
72 Correct 248 ms 58024 KB Output is correct
73 Correct 1134 ms 90952 KB Output is correct
74 Correct 2792 ms 69040 KB Output is correct
75 Correct 1686 ms 91212 KB Output is correct
76 Correct 1970 ms 103876 KB Output is correct