oj.uz

Submission #948476

# Submission time Handle Problem Language Result Execution time Memory
948476 2024-03-18T06:53:08 Z dimashhh Joker (BOI20_joker) C++17
0 / 100
 60 ms 19072 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 2e5 + 5, MOD = 998244353;

int p[N],sz[N],n,m,q,d[N];
void reset(){
    for(int i = 1;i <= n;i++){
        sz[i] = 1;
        p[i] = i;
        d[i] = 0;
    }
}
pair<int, int> get(int v) {
    if(p[v] == v){
        return {v,0};
    }
    pair<int,int> x = get(p[v]);
    return {x.first,d[v]+x.second};
}
vector<array<int,5>> st;
bool merge(int a,int b){
    pair<int,int> x = get(a),y = get(b);
    if(sz[x.first] < sz[y.first]){
        swap(x,y);
    }
    a = x.first;
    b = y.first;
    if(a == b){
        if(x.second % 2 == y.second % 2){
            st.push_back({a,b,-1,1,0});
            return true;
        }
        st.push_back({a,b,-1,0,0});
        return false;
    }
    st.push_back({a,b,sz[a],p[b],d[b]});
    p[b] = a;
    sz[a] += sz[b];
    d[b] = (x.second % 2 == y.second % 2);
    return false;
}
int rr[N],cur_col = 0;
void roll_back(){
    auto dd = st.back();
    st.pop_back();
    if(dd[2] == -1){
        cur_col -= dd[3];
        return;
    }
    sz[dd[0]] = dd[2];
    p[dd[1]] = dd[3];
    d[dd[1]] = dd[4];
}
int check_rb(){
    auto dd = st.back();
    if(dd[2] != -1) return 0;
    return dd[3];
}
int check_merge(int a,int b){
    pair<int,int> x = get(a),y = get(b);
    if(x.first != x.second) return 0;
    return (x.second % 2 == y.second % 2);
}
int x[N],y[N];
vector<pair<int,int>> qr[N];
vector<int> ids[N];
bool ans[N];
void precalc(){
    reset();
    for(int i = m;i >= 1;i--){
        cur_col += merge(x[i],y[i]);
        if(cur_col){
            rr[0] = i;
            break;
        }
    }
    if(rr[0] == 0){
        return;
    }
//    cout << 0 << ' ' << rr[0] << '\n';
    for(int i = 1;i <= m;i++){
        rr[i] = rr[i - 1];
        cur_col += check_merge(x[i],y[i]);
//        cout << cur_col << '\n';
        while(rr[i] <= m && cur_col - check_rb() >= 1){
            roll_back();
            rr[i]++;
        }
        merge(x[i],y[i]);
//        cout << i << ' ' << rr[i] << '\n';
    }
}
void test(){
    cin >> n >> m >> q;
    for(int i = 1;i <= m;i++){
        cin >> x[i] >> y[i];
    }
    precalc();
    for(int i = 1;i <=q;i++){
        int l,r;
        cin >> l >> r;
        cout << (rr[l] >= r ? "YES\n":"NO\n");
    }
}
int main(){
    ios_base::sync_with_stdio(false);cin.tie(0);
    int T = 1;
//    cin >> T;
    while(T--){
        test();
    }
}

Subtask #1
0 / 6.0

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

Subtask #2
0 / 8.0

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

Subtask #3
0 / 25.0

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

Subtask #4
0 / 10.0

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

Subtask #5
0 / 22.0

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

Subtask #6
0 / 29.0

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