oj.uz

Submission #751947

# Submission time Handle Problem Language Result Execution time Memory
751947 2023-06-01T23:26:39 Z Ronin13 Joker (BOI20_joker) C++14
0 / 100
 159 ms 8844 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 gg;
void divi(int l1, int l2, int r1, int r2){
    if(l1 > l2) return;
    int m = (l1 + l2) / 2;
    int S = st.size();
    bool pg = gg;
    for(int i = l1; i < m; i++){
        gg &= union_sets(u[i], v[i]);
    }
    if(!gg){
        ans[m] = r2;
    }
    else{
        for(int i = r2; i >= r1; i--){
            if(!gg) {
                ans[m] = i;
                break;
            }
            gg &= union_sets(u[i], v[i]);
        }
        ans[m] = r1;
    }
    rollback(S);
    gg = pg;
    for(int i = l1; i <= m; i++){
        gg &= union_sets(u[i], v[i]);
    }
    divi(m + 1, l2, ans[m], r2);
    gg = pg;
    rollback(S);
    for(int i = r2; i > ans[m]; i--){
        gg &= union_sets(u[i], v[i]);
    }
    divi(l1, m - 1, r1, ans[m]);
    rollback(S);
    gg = pg;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0);
    gg = 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, 0, m);
   /* for(int i = 1; i <= m ;i++)
        cout << ans[i] << ' ';*/
    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 340 KB Output is correct
3 Incorrect 0 ms 340 KB Output isn't correct
4 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 340 KB Output is correct
3 Incorrect 0 ms 340 KB Output isn't correct
4 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 340 KB Output is correct
3 Incorrect 159 ms 8844 KB Output isn't correct
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 340 KB Output is correct
3 Incorrect 0 ms 340 KB Output isn't correct
4 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 340 KB Output is correct
3 Incorrect 0 ms 340 KB Output isn't correct
4 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 340 KB Output is correct
3 Incorrect 0 ms 340 KB Output isn't correct
4 Halted 0 ms 0 KB -