Submission #1045697

#	Time	Username	Problem	Language	Result	Execution time	Memory
1045697		hirayuu_oj	Joker (BOI20_joker)	C++17	49 / 100	2033 ms	29260 KiB

Joker

#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define rng(i,l,r) for(int i=(l); i<(r); i++)
#define all(x) x.begin(),x.end()
using ll=long long;

struct odd_cycle {
    int size;
    vector<int> uni;
    int time;
    stack<array<int,4>> memo;
    bool isok;
    odd_cycle(int sz) {
        size=sz;
        time=0;
        isok=false;
        memo.push({-1,-1,0,-1});
        uni.resize(size*2,-1);
    }
    int leader(int p) {
        while(uni[p]>=0)p=uni[p];
        return p;
    }
    void merge(pair<int,int> x) {
        if(isok) {
            time++;
            return;
        }
        int u=x.first;
        int v=x.second;
        int a=leader(u),d=leader(v+size);
        if(-uni[a]>-uni[d])swap(a,d);
        if(a!=d) {
            memo.push({a,uni[a],isok,time});
            memo.push({d,uni[d],isok,time});
            uni[d]+=uni[a];
            uni[a]=d;
        }
        int b=leader(v),c=leader(u+size);
        if(-uni[b]>-uni[c])swap(b,c);
        if(b!=c) {
            memo.push({b,uni[b],isok,time});
            memo.push({c,uni[c],isok,time});
            uni[c]+=uni[b];
            uni[b]=c;
        }
        if(leader(u)==leader(u+size))isok=true;
        time++;
    }
    void undo() {
        time--;
        while(memo.top()[3]==time) {
            isok=memo.top()[2];
            uni[memo.top()[0]]=memo.top()[1];
            memo.pop();
        }
    }

};
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N,M,Q;
    cin>>N>>M>>Q;
    const int backet=316;
    vector<pair<int,int>> edge(M);
    rep(i,M) {
        int u,v;
        cin>>u>>v;
        edge[i]={u-1,v-1};
    }
    vector<vector<array<int,3>>> query(3+M/backet);
    rep(i,Q) {
        int l,r;
        cin>>l>>r;
        query[(l-1)/backet].push_back({-r,l-1,i});
    }
    vector<string> ans(Q);
    rep(i,3+M/backet) {
        if(query[i].empty())continue;
        sort(all(query[i]));
        odd_cycle uni(N);
        rep(j,backet*i)uni.merge(edge[j]);
        int ri=M;
        rep(j,query[i].size()) {
            int r=-query[i][j][0];
            int l=query[i][j][1];
            int ind=query[i][j][2];
            rng(k,r,ri) {
                uni.merge(edge[k]);
            }
            ri=r;
            rep(k,l%backet) {
                uni.merge(edge[i*backet+k]);
            }
            if(uni.isok)ans[ind]="YES";
            else ans[ind]="NO";
            rep(k,l%backet) {
                uni.undo();
            }
        }
    }
    rep(i,Q) {
        cout<<ans[i]<<"\n";
    }
}

Compilation message (stderr)

Joker.cpp: In function 'int main()':
Joker.cpp:3:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    3 | #define rep(i,n) for(int i=0; i<(n); i++)
      |                                ^
Joker.cpp:86:9: note: in expansion of macro 'rep'
   86 |         rep(j,query[i].size()) {
      |         ^~~

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