Submission #948636

#	Time	Username	Problem	Language	Result	Execution time	Memory
948636		dimashhh	Joker (BOI20_joker)	C++17	0 / 100	2097 ms	12488 KiB

Joker

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

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

int p[N],sz[N],n,m,q,d[N];
int cur_col = 0;
void reset(){
    cur_col = 0;
    for(int i = 1;i <= m;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});
            cur_col++;
            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;
}
queue<array<int,4>> qr;
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 x[N],y[N],R[N];
void go(int l,int r,int _l,int _r){
    if(l > r) return;
    int t = (l + r) >> 1;
    int c = 0,c1 = 0;
    for(int i = l;i < t;++i){
        merge(x[i],y[i]);
    }
    R[t] = _r;
    while(R[t] >= t && cur_col == 0){
        c1++;
        merge(x[R[t]],y[R[t]]);
        R[t]--;
    }
    for(int i = 0;i < c1;i++){
        roll_back();
    }
    merge(x[t],y[t]);
    go(t+1,r,R[t],_r);
    for(int i = l;i <= t;i++){
        roll_back();
    }
    for(int i = _r;i > R[t];i--){
        merge(x[i],y[i]);
    }
    go(l,t-1,_l,R[t]);
}
void test(){
    cin >> n >> m >> q;
    for(int i = 1;i <= m;i++){
        cin >> x[i] >> y[i];
    }
    reset();
    go(1,m,1,m);
    reset();
    for(int i = 1;i <= m;i++){
        for(int j = 1;j < i;j++){
            merge(x[j],y[j]);
        }
        R[i] = m;
        int c1 = 0;
        while(R[i] >= i && cur_col == 0){
            merge(x[R[i]],y[R[i]]);
            c1++;
            R[i]--;
        }
//        cout << c1 << "x\n";
        for(int j = 0;j < c1 + i - 1;j++){
            roll_back();
        }
    }
    for(int i =1 ;i <= m;i++){
        R[i]++;
    }
    for(int i = 1;i <= q;i++){
        int l,r;
        cin >> l >> r;
        cout << (r < R[l] ? "YES\n":"NO\n");
    }
}
int main(){
    ios_base::sync_with_stdio(false);cin.tie(0);
    int T = 1;
//    cin >> T;
    while(T--){
        test();
    }
}

Compilation message (stderr)

Joker.cpp: In function 'void go(int, int, int, int)':
Joker.cpp:65:9: warning: unused variable 'c' [-Wunused-variable]
   65 |     int c = 0,c1 = 0;
      |         ^

• Subtask 1: 0 / 6
• Subtask 2: 0 / 8
• Subtask 3: 0 / 25
• Subtask 4: 0 / 10
• Subtask 5: 0 / 22
• Subtask 6: 0 / 29