oj.uz

Submission #1038430

# Submission time Handle Problem Language Result Execution time Memory
1038430 2024-07-29T19:20:27 Z _8_8_ Game (APIO22_game) C++17
2 / 100
 44 ms 106072 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;
}
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;
    bool ok = false,ok1 = false;
    function<void(int)> dfs = [&](int u){
        R[v].insert(u);
        _r[u].push_back(tm);
        ok = 1;
        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()) {
        if(L[v].find(y) != L[v].end()) {
            CYC = 1;
            return;
        }
        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;
    };
    if(L[v].find(y) != L[v].end()) {
        if(R[v].find(x) != R[v].end()) {
            CYC = 1;
            return;
        }
        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) {
        addl(u,v,v1,tl1,tr1,prev1);
        add(u,v,v2,tl2,tr2,prev2);
        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 << "x\n";
    return CYC;
}

Compilation message

game.cpp: In function 'void add(int, int, int&, int&, int&, int&)':
game.cpp:47:21: warning: unused variable 'ok1' [-Wunused-variable]
   47 |     bool ok = false,ok1 = false;
      |                     ^~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 106068 KB Output is correct
2 Correct 38 ms 106072 KB Output is correct
3 Correct 38 ms 106064 KB Output is correct
4 Correct 39 ms 106072 KB Output is correct
5 Correct 39 ms 106064 KB Output is correct
6 Correct 38 ms 106072 KB Output is correct
7 Correct 40 ms 106072 KB Output is correct

Subtask #2
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 106068 KB Output is correct
2 Correct 38 ms 106072 KB Output is correct
3 Correct 38 ms 106064 KB Output is correct
4 Correct 39 ms 106072 KB Output is correct
5 Correct 39 ms 106064 KB Output is correct
6 Correct 38 ms 106072 KB Output is correct
7 Correct 40 ms 106072 KB Output is correct
8 Correct 39 ms 106064 KB Output is correct
9 Correct 39 ms 106072 KB Output is correct
10 Correct 44 ms 105924 KB Output is correct
11 Correct 39 ms 106064 KB Output is correct
12 Correct 39 ms 105988 KB Output is correct
13 Incorrect 41 ms 106032 KB Wrong Answer[1]
14 Halted 0 ms 0 KB -

Subtask #3
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 106068 KB Output is correct
2 Correct 38 ms 106072 KB Output is correct
3 Correct 38 ms 106064 KB Output is correct
4 Correct 39 ms 106072 KB Output is correct
5 Correct 39 ms 106064 KB Output is correct
6 Correct 38 ms 106072 KB Output is correct
7 Correct 40 ms 106072 KB Output is correct
8 Correct 39 ms 106064 KB Output is correct
9 Correct 39 ms 106072 KB Output is correct
10 Correct 44 ms 105924 KB Output is correct
11 Correct 39 ms 106064 KB Output is correct
12 Correct 39 ms 105988 KB Output is correct
13 Incorrect 41 ms 106032 KB Wrong Answer[1]
14 Halted 0 ms 0 KB -

Subtask #4
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 106068 KB Output is correct
2 Correct 38 ms 106072 KB Output is correct
3 Correct 38 ms 106064 KB Output is correct
4 Correct 39 ms 106072 KB Output is correct
5 Correct 39 ms 106064 KB Output is correct
6 Correct 38 ms 106072 KB Output is correct
7 Correct 40 ms 106072 KB Output is correct
8 Correct 39 ms 106064 KB Output is correct
9 Correct 39 ms 106072 KB Output is correct
10 Correct 44 ms 105924 KB Output is correct
11 Correct 39 ms 106064 KB Output is correct
12 Correct 39 ms 105988 KB Output is correct
13 Incorrect 41 ms 106032 KB Wrong Answer[1]
14 Halted 0 ms 0 KB -

Subtask #5
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 106068 KB Output is correct
2 Correct 38 ms 106072 KB Output is correct
3 Correct 38 ms 106064 KB Output is correct
4 Correct 39 ms 106072 KB Output is correct
5 Correct 39 ms 106064 KB Output is correct
6 Correct 38 ms 106072 KB Output is correct
7 Correct 40 ms 106072 KB Output is correct
8 Correct 39 ms 106064 KB Output is correct
9 Correct 39 ms 106072 KB Output is correct
10 Correct 44 ms 105924 KB Output is correct
11 Correct 39 ms 106064 KB Output is correct
12 Correct 39 ms 105988 KB Output is correct
13 Incorrect 41 ms 106032 KB Wrong Answer[1]
14 Halted 0 ms 0 KB -