Submission #1106650

#	Time	Username	Problem	Language	Result	Execution time	Memory
1106650		koukirocks	Joker (BOI20_joker)	C++17	100 / 100	133 ms	21436 KiB

Joker

#include <bits/stdc++.h>
#define speed ios_base::sync_with_stdio(0); cin.tie(0)
#define all(x) (x).begin(),(x).end()
#define F first
#define S second
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx,avx2")
//#pragma GCC target("popcnt")
 
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
 
const ll MAX=2e5+10,P=1e9+7;
const ll INF=0x3f3f3f3f,oo=0x3f3f3f3f3f3f3f3f;
const ldb eps=1e-6;
const ldb PI=acos(-1.0);
const int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
template<typename T>
using vvector = vector<vector<T>>;

struct DSU {
    int n;
    vector<ll> fa,sz;
    vector<pll> lnk;
    vector<bool> rev;
    bool isbip;
    DSU(int n):n(n),isbip(true) {
        fa.resize(n+1);
        iota(all(fa),0);
        sz.resize(n+1,1);
        rev.resize(n+1);
    }
    pair<int,bool> get(ll x) {
        if (fa[x]==x) return {x,rev[x]};
        pair<int,bool> now = get(fa[x]);
        return {now.F,now.S^rev[x]};
    }
    void link(int a,int b) {
        auto [na,ra]=get(a);
        auto [nb,rb]=get(b);
        // cout<<na<<" "<<nb<<" nab\n"<<flush;
        // cout<<ra<<" "<<rb<<" rab\n"<<flush;
        if (na==nb) {
            if (ra==rb) {
                isbip=false;
                lnk.emplace_back(-1,-1);
            }
            return;
        }
        if (sz[na]>sz[nb]) {
            swap(na,nb);
            swap(ra,rb);
        }
        fa[na]=nb;
        rev[na]=!(ra^rb);
        sz[nb]+=sz[na];
        lnk.emplace_back(na,nb);
    }
    void unlink() {                                                                                                                                                                                                                                                                    ;
        auto [a,b] = lnk.back();
        if (a==-1) isbip=true;
        else {
            rev[a]=false;
            sz[b]-=sz[a];
            fa[a]=a;
        }
        lnk.pop_back();
    }
};

void del(int sz,DSU &d) {
    // cout<<d.lnk.size()<<" "<<sz<<" sz\n"<<flush;
    while (d.lnk.size()>sz) {
        d.unlink();
        // cout<<d.lnk.size()<<" "<<sz<<" sz\n"<<flush;
    }
}

void getall(DSU &d) {
    for (int i=1;i<=d.n;i++) {
        cout<<d.get(i).F<<" ";
    }
    cout<<" all fa\n";
    for (int i=1;i<=d.n;i++) {
        cout<<d.get(i).S<<" ";
    }
    cout<<" all rev\n";
}

void cal(int l,int r,int fl,int fr,vector<ll> &ans,vector<pll> &E,DSU &d) {
    if (l>r or fl>fr) return;
    if (fl==fr) {
        for (int i=l;i<=r;i++) {
            ans[i]=fl;
        }
        return ;
    }
    // cout<<l<<" "<<r<<" "<<fl<<" "<<fr<<" "<<"lr flr start\n"<<flush;
    // getall(d);
    int mid=l+r>>1;
    // r+1 ~ fl
    int sz=d.lnk.size();
    for (int i=mid;i<=min(fl,r);i++) {
        // cout<<i<<" lk1\n";
        d.link(E[i].F,E[i].S);
    }
    // mid ~ fl
    // getall(d);
    int sz2=d.lnk.size();
    ans[mid]=-1;
    
    // cout<<l<<" "<<r<<" lr start2\n"<<flush;
    for (int i=fl+1;i<=fr;i++) {
        // getall(d);
        // cout<<i<<" lk2\n";
        d.link(E[i].F,E[i].S);
        if (!d.isbip) {
            ans[mid]=i-1;
            // cout<<mid<<" "<<ans[mid]<<" mid ans\n";
            break;
        }
    }
    if (ans[mid]==-1) ans[mid]=fr;
    // mid ~ ans[mid]
    del(sz2,d);
    // mid ~ fl
    cal(l,mid-1,fl,ans[mid],ans,E,d);
    del(sz,d);
    // r+1 ~ fl
    // getall(d);
    // cout<<l<<" "<<r<<" lr start3\n"<<flush;
    for (int i=max(fl,r)+1;i<=ans[mid];i++) {
        // cout<<i<<" Ei\n"<<flush;
        // cout<<i<<" lk3\n";
        d.link(E[i].F,E[i].S);
    }
    // cout<<l<<" "<<r<<" lr start4\n"<<flush;
    cal(mid+1,r,ans[mid],fr,ans,E,d);
    // cout<<l<<" "<<r<<" lr start5\n"<<flush;
    del(sz,d);
}

int main() {
    speed;
    int n,m,q;
    cin>>n>>m>>q;
    vector<pll> E(2*m+10);
    vector<ll> dp(m+10);
    DSU d(n);
    for (int i=1;i<=m;i++) {
        cin>>E[i].F>>E[i].S;
        E[i+m]=E[i];
    }
    cal(2,m+1,m-1,2*m,dp,E,d);
    // for (int i=2;i<=m+1;i++) cout<<dp[i]<<" ";
    // cout<<" dp\n";
    while (q--) {
        int l,r;
        cin>>l>>r;
        if (l+m-1<=dp[r+1]) cout<<"NO\n";
        else cout<<"YES\n";
    }
    return 0;
}

/*
7 7 0
1 2
2 3
3 4
4 5
5 6
6 7
5 7
*/

Compilation message (stderr)

Joker.cpp: In function 'void del(int, DSU&)':
Joker.cpp:78:24: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   78 |     while (d.lnk.size()>sz) {
      |            ~~~~~~~~~~~~^~~
Joker.cpp: In function 'void cal(int, int, int, int, std::vector<long long int>&, std::vector<std::pair<long long int, long long int> >&, DSU&)':
Joker.cpp:105:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  105 |     int mid=l+r>>1;
      |             ~^~

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