oj.uz

Submission #1038680

# Submission time Handle Problem Language Result Execution time Memory
1038680 2024-07-30T06:04:33 Z _8_8_ Game (APIO22_game) C++17
12 / 100
 139 ms 191056 KB 
#include "game.h"

#include <bits/stdc++.h>
using namespace std;
 
const int N = 3e5 + 12;
vector<int> g[N],gr[N];
set<int> L[N * 3],R[N * 3];
int k;
int nn;
void build(int v = 1,int tl = 0,int tr = k - 1) {
    if(tl > tr) return;
    int tm = (tl + tr) >> 1;
    for(int i = tl;i <= tr;i++) {
        if(i <= tm) {
            L[v].insert(i);
        }   
        if(i >= tm) {
            R[v].insert(i);
        }
    }
    if(tl == tr) return;
    build(v + v,tl,tm - 1);
    build(v + v + 1,tm + 1,tr);
}
void init(int n, int K) {
    k = K;
    nn = n;
    for(int i = 0;i <= k - 2;i++) {
        g[i].push_back(i + 1);
        gr[i + 1].push_back(i); 
    }
    build();
}
bool CYC = false;
vector<int>_r[N];
bool check(int tm,int prev,int v,int val) {
    if(prev == -1) return 1;
    if(prev < tm && R[v / 2].find(val) == R[v / 2].end()) return false;
    if(prev > tm && L[v / 2].find(val) == L[v / 2].end()) return false;
    return 1;
}
set<int> bfl[N * 3],bfr[N * 3];
void add(int x,int y,int &v,int &tl,int &tr,int &prev) {
    if(tl > tr) return;
    if(CYC) return;
    int tm = (tl + tr) >> 1;
    function<void(int)> dfs = [&](int u){
        R[v].insert(u);
        _r[u].push_back(tm);
        // cout << tm << ' ' << u << "R\n";
        if(L[v].find(u) != L[v].end()) {
            CYC = 1;
            return;
        }
        for(int to:g[u]) {
            if(R[v].find(to) == R[v].end() && check(tm,prev,v,to)) {
                dfs(to);
            }
            if(CYC) return;
        }
        if(CYC) return;
    };
    if(R[v].find(x) != R[v].end()) bfr[v].insert(y);
    auto it = bfr[v].begin();
    bool ok = false;
    while(it != bfr[v].end()) {
        if(R[v].find(*it) != R[v].end()){
            it = bfr[v].erase(it);
            ok = 1;
            continue;
        }
        if(R[v].find(*it) == R[v].end() && check(tm,prev,v,*it)) {
            dfs(*it);
            ok = 1;
            it = bfr[v].erase(it);
        }else {
            it++;
        }
    }
    if(ok) {
        if(check(tm,prev,v,y) && R[v].find(y) == R[v].end()) dfs(y);
        v = v + v + 1;
        tl = tm + 1;
        prev = tm;
    } else {
        v += v;
        tr = tm - 1;
        prev = tm;
    }
}
void addl(int x,int y,int &v,int &tl,int &tr,int &prev) {
    if(tl > tr) return;
    if(CYC) return;
    int tm = (tl + tr) >> 1;
    function<void(int)> dfs1 = [&](int u){
        if(R[v].find(u) != R[v].end()) {
            CYC = 1;
            return;
        }
        L[v].insert(u);
        for(int to:gr[u]) {
            if(L[v].find(to) == L[v].end() && (check(tm,prev,v,to))) {
                dfs1(to);
            }
            if(CYC) return;
        }
        if(CYC) return;
    };
    bool ok = false;
    if(L[v].find(y) != L[v].end()) {
        bfl[v].insert(x);
    }
    auto it = bfl[v].begin();
    while(it != bfl[v].end()) {
        if(L[v].find(*it)!=L[v].end()){
            ok = 1;
            it = bfl[v].erase(it);
            continue;
        }
        if(check(tm,prev,v,*it)) {
            dfs1(*it);
            it = bfl[v].erase(it);
            ok = 1;
        }else {
            it++;
        }
    }
    if(ok) {
        if(L[v].find(x) == L[v].end() && (check(tm,prev,v,x))) dfs1(x);
        v += v;
        tr = tm - 1;
        prev = tm;
    } else {
        v = v + v + 1;
        tl = tm + 1;
        prev = tm;
    }
}
void _add(int u,int v) {
    int v1 = 1,tl1 = 0,tr1 = k - 1,prev1 = -1;
    int v2 = 1,tl2 = 0,tr2 = k - 1,prev2 = -1;
    while(tl1 <= tr1 || tl2 <= tr2) {
        add(u,v,v2,tl2,tr2,prev2);
        addl(u,v,v1,tl1,tr1,prev1);
        if(CYC) break;
    }
}
int add_teleporter(int u, int v) {
    if(max(u,v) <= k - 1) {
        if(u >= v) {
            CYC = 1;
            return 1;
        }
        return 0;
    }
    if(CYC) return 1;
    g[u].push_back(v);
    gr[v].push_back(u);
    _add(u,v);
    // cout << "_____________\n";
    return CYC;
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 190544 KB Output is correct
2 Correct 74 ms 190544 KB Output is correct
3 Correct 73 ms 190456 KB Output is correct
4 Correct 74 ms 190544 KB Output is correct
5 Correct 72 ms 190544 KB Output is correct
6 Correct 70 ms 190544 KB Output is correct
7 Correct 74 ms 190492 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 190544 KB Output is correct
2 Correct 74 ms 190544 KB Output is correct
3 Correct 73 ms 190456 KB Output is correct
4 Correct 74 ms 190544 KB Output is correct
5 Correct 72 ms 190544 KB Output is correct
6 Correct 70 ms 190544 KB Output is correct
7 Correct 74 ms 190492 KB Output is correct
8 Correct 74 ms 190544 KB Output is correct
9 Correct 73 ms 190600 KB Output is correct
10 Correct 78 ms 190628 KB Output is correct
11 Correct 73 ms 190544 KB Output is correct
12 Correct 73 ms 190544 KB Output is correct
13 Correct 77 ms 190632 KB Output is correct
14 Correct 72 ms 190464 KB Output is correct
15 Correct 73 ms 190544 KB Output is correct
16 Correct 72 ms 190544 KB Output is correct
17 Correct 73 ms 190580 KB Output is correct
18 Correct 73 ms 190568 KB Output is correct
19 Correct 72 ms 190604 KB Output is correct

Subtask #3
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 190544 KB Output is correct
2 Correct 74 ms 190544 KB Output is correct
3 Correct 73 ms 190456 KB Output is correct
4 Correct 74 ms 190544 KB Output is correct
5 Correct 72 ms 190544 KB Output is correct
6 Correct 70 ms 190544 KB Output is correct
7 Correct 74 ms 190492 KB Output is correct
8 Correct 74 ms 190544 KB Output is correct
9 Correct 73 ms 190600 KB Output is correct
10 Correct 78 ms 190628 KB Output is correct
11 Correct 73 ms 190544 KB Output is correct
12 Correct 73 ms 190544 KB Output is correct
13 Correct 77 ms 190632 KB Output is correct
14 Correct 72 ms 190464 KB Output is correct
15 Correct 73 ms 190544 KB Output is correct
16 Correct 72 ms 190544 KB Output is correct
17 Correct 73 ms 190580 KB Output is correct
18 Correct 73 ms 190568 KB Output is correct
19 Correct 72 ms 190604 KB Output is correct
20 Correct 69 ms 190544 KB Output is correct
21 Correct 73 ms 190544 KB Output is correct
22 Correct 82 ms 190800 KB Output is correct
23 Correct 75 ms 190640 KB Output is correct
24 Correct 74 ms 190800 KB Output is correct
25 Correct 132 ms 191056 KB Output is correct
26 Correct 92 ms 191056 KB Output is correct
27 Correct 139 ms 191040 KB Output is correct
28 Incorrect 108 ms 190800 KB Wrong Answer[1]
29 Halted 0 ms 0 KB -

Subtask #4
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 190544 KB Output is correct
2 Correct 74 ms 190544 KB Output is correct
3 Correct 73 ms 190456 KB Output is correct
4 Correct 74 ms 190544 KB Output is correct
5 Correct 72 ms 190544 KB Output is correct
6 Correct 70 ms 190544 KB Output is correct
7 Correct 74 ms 190492 KB Output is correct
8 Correct 74 ms 190544 KB Output is correct
9 Correct 73 ms 190600 KB Output is correct
10 Correct 78 ms 190628 KB Output is correct
11 Correct 73 ms 190544 KB Output is correct
12 Correct 73 ms 190544 KB Output is correct
13 Correct 77 ms 190632 KB Output is correct
14 Correct 72 ms 190464 KB Output is correct
15 Correct 73 ms 190544 KB Output is correct
16 Correct 72 ms 190544 KB Output is correct
17 Correct 73 ms 190580 KB Output is correct
18 Correct 73 ms 190568 KB Output is correct
19 Correct 72 ms 190604 KB Output is correct
20 Correct 69 ms 190544 KB Output is correct
21 Correct 73 ms 190544 KB Output is correct
22 Correct 82 ms 190800 KB Output is correct
23 Correct 75 ms 190640 KB Output is correct
24 Correct 74 ms 190800 KB Output is correct
25 Correct 132 ms 191056 KB Output is correct
26 Correct 92 ms 191056 KB Output is correct
27 Correct 139 ms 191040 KB Output is correct
28 Incorrect 108 ms 190800 KB Wrong Answer[1]
29 Halted 0 ms 0 KB -

Subtask #5
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 190544 KB Output is correct
2 Correct 74 ms 190544 KB Output is correct
3 Correct 73 ms 190456 KB Output is correct
4 Correct 74 ms 190544 KB Output is correct
5 Correct 72 ms 190544 KB Output is correct
6 Correct 70 ms 190544 KB Output is correct
7 Correct 74 ms 190492 KB Output is correct
8 Correct 74 ms 190544 KB Output is correct
9 Correct 73 ms 190600 KB Output is correct
10 Correct 78 ms 190628 KB Output is correct
11 Correct 73 ms 190544 KB Output is correct
12 Correct 73 ms 190544 KB Output is correct
13 Correct 77 ms 190632 KB Output is correct
14 Correct 72 ms 190464 KB Output is correct
15 Correct 73 ms 190544 KB Output is correct
16 Correct 72 ms 190544 KB Output is correct
17 Correct 73 ms 190580 KB Output is correct
18 Correct 73 ms 190568 KB Output is correct
19 Correct 72 ms 190604 KB Output is correct
20 Correct 69 ms 190544 KB Output is correct
21 Correct 73 ms 190544 KB Output is correct
22 Correct 82 ms 190800 KB Output is correct
23 Correct 75 ms 190640 KB Output is correct
24 Correct 74 ms 190800 KB Output is correct
25 Correct 132 ms 191056 KB Output is correct
26 Correct 92 ms 191056 KB Output is correct
27 Correct 139 ms 191040 KB Output is correct
28 Incorrect 108 ms 190800 KB Wrong Answer[1]
29 Halted 0 ms 0 KB -