Submission #560102

#	Time	Username	Problem	Language	Result	Execution time	Memory
560102		abcvuitunggio	Joker (BOI20_joker)	C++17	100 / 100	199 ms	13368 KiB

Joker

#include <iostream>
#include <vector>
using namespace std;
struct state{
    int u,pu,v,pv;
};
int n,m,t,p[200001],f[200001],d[200001],a[200001],b[200001],l,r;
vector <state> q;
pair <int, int> findp(int i){
    int x=0;
    while (p[i]!=i){
        x^=f[i];
        i=p[i];
    }
    return {i,x};
}
bool unite(int i, int j){
    auto pi=findp(i),pj=findp(j);
    if (pi.first==pj.first)
        return (pi.second!=pj.second);
    q.push_back({pi.first,pi.first,pj.first,pj.first});
    if (pi.first>pj.first)
        swap(pi,pj);
    p[pi.first]=pj.first;
    f[pi.first]=pi.second^pj.second^1;
    return true;
}
void rollback(int sz){
    while (q.size()>sz){
        state s=q.back();
        q.pop_back();
        p[s.u]=s.pu;
        p[s.v]=s.pv;
    }
}
void cal(int l, int r, int optl, int optr){
    if (l>r)
        return;
    int mid=(l+r)>>1,ch=1;
    int s=q.size();
    for (int i=max(l,1);i<=mid;i++)
        if (!unite(a[i],b[i])){
            ch=0;
            break;
        }
    if (ch){
        int s2=q.size();
        d[mid]=0;
        for (int i=min(optr,m);i>=max(optl,mid+1);i--)
            if (!unite(a[i],b[i])){
                d[mid]=i;
                break;
            }

        rollback(s2);
        cal(mid+1,r,d[mid],optr);
    }
    rollback(s);
    for (int i=d[mid]+1;i<=optr;i++)
        unite(a[i],b[i]);
    cal(l,mid-1,optl,d[mid]);
    rollback(s);
}
int main(){
    ios_base::sync_with_stdio(NULL);cin.tie(nullptr);
    cin >> n >> m >> t;
    for (int i=1;i<=n;i++)
        p[i]=i;
    for (int i=1;i<=m;i++){
        cin >> a[i] >> b[i];
        d[i]=m+1;
    }
    cal(0,m,1,m+1);
    while (t--){
        cin >> l >> r;
        cout << (d[l-1]>=r+1?"YES\n":"NO\n");
    }
}

Compilation message (stderr)

Joker.cpp: In function 'void rollback(int)':
Joker.cpp:29:20: warning: comparison of integer expressions of different signedness: 'std::vector<state>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   29 |     while (q.size()>sz){
      |            ~~~~~~~~^~~

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