oj.uz

Submission #751939

# Submission time Handle Problem Language Result Execution time Memory
751939 2023-06-01T22:56:47 Z Ronin13 Joker (BOI20_joker) C++14
0 / 100
 2000 ms 8304 KB 
#include <bits/stdc++.h>
#define ll long long
#define f first
#define s second
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
#define ull unsigned ll
#define pii pair<int,int>
using namespace std;
const int nmax = 400001;

stack <pair<pair<int, bool> , pair<int, bool> > > st;

pii p[nmax];
int sz[nmax];
bool good[nmax];
void make_set(int v){
    p[v] = {v, 0};
    sz[v] = 1;
    good[v] = true;
}

pair <int,int> find_set(int v){
    if(v == p[v].f){
        return {v, 0};
    }
    pii x = find_set(p[v].f);
    return {x.f, x.s ^ p[v].s};
}

bool union_sets(int a, int b){
    pii A = find_set(a);
    pii B = find_set(b);
    if(A.f == B.f){
        st.push({{A.f, good[A.f]}, {A.f, good[A.f]}});
        good[A.f] &= (A.s != B.s);
        return good[A.f];
    }
    if(sz[A.f] < sz[B.f])
        swap(A, B);
    st.push({{B.f, good[B.f]}, {A.f, good[A.f]}});
    good[A.f] &= good[B.f];
    sz[A.f] += sz[B.f];
    p[B.f] = {A.f, A.s ^ B.s ^ 1};

    return good[A.f];
}

void rollback(int Sz){
    while(st.size() > Sz){
        int x = st.top().f.f;
        p[x] = {x, 0};
      if(x != st.top().s.f){
        good[x] = st.top().f.s;
        good[st.top().s.f] = st.top().s.s;
        sz[st.top().s.f] -=sz[st.top().f.f];}
        st.pop();
    }
}

int u[nmax], v[nmax];
int ans[nmax];
bool good1;
void divi(int l1, int l2, int r1, int r2){
    if(l1 > l2) return;
    int m = (l1 + l2) / 2;
    int s1 = st.size();
    bool good = good1;
    bool pr = good1;
    for(int i = l1; i < m; i++)
        good &= union_sets(u[i], v[i]);
    good1 = good;
    int s = st.size();
    ans[m] = m;
    for(int i = r2; i >= r1; i--){
        if(!good){ ans[m] = i + 1; break;}
        if(i == m){
            ans[m] = i;
            break;
        }
        good &= union_sets(u[i], v[i]);
    }
    rollback(s);
    good1 &= union_sets(u[m], v[m]);
    divi(m + 1, l2, ans[m], r2);
    rollback(s1);
    int s2 = st.size();
    bool pr1 = pr;
    good1 = pr;
    for(int i = r2; i > ans[m]; i--){
        good1 &= union_sets(v[i], u[i]);
    }
    divi(l1, m - 1, r1, ans[m]);
    rollback(s2);
    good1 = pr1;
}

int main(){
    good1 = true;
    int n, m, q; cin >> n >> m >> q;
    for(int i = 1; i <= n; i++)
        make_set(i);
    for(int i = 1; i <= m; i++){
        cin >> u[i] >> v[i];
    }
    divi(1, m, 1, m);

    while(q--){
        int l, r; cin >>l >> r;
        r < ans[l] ? cout << "YES\n" : cout << "NO\n";
    }
}

Compilation message

Joker.cpp: In function 'void rollback(int)':
Joker.cpp:51:21: warning: comparison of integer expressions of different signedness: 'std::stack<std::pair<std::pair<int, bool>, std::pair<int, bool> > >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   51 |     while(st.size() > Sz){
      |           ~~~~~~~~~~^~~~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 312 KB Output is correct
3 Correct 0 ms 312 KB Output is correct
4 Incorrect 0 ms 340 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 312 KB Output is correct
3 Correct 0 ms 312 KB Output is correct
4 Incorrect 0 ms 340 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 312 KB Output is correct
3 Execution timed out 2039 ms 8304 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 312 KB Output is correct
3 Correct 0 ms 312 KB Output is correct
4 Incorrect 0 ms 340 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 312 KB Output is correct
3 Correct 0 ms 312 KB Output is correct
4 Incorrect 0 ms 340 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 312 KB Output is correct
3 Correct 0 ms 312 KB Output is correct
4 Incorrect 0 ms 340 KB Output isn't correct
5 Halted 0 ms 0 KB -