Submission #443328

#	Time	Username	Problem	Language	Result	Execution time	Memory
443328		Nima_Naderi	Joker (BOI20_joker)	C++14	100 / 100	960 ms	18880 KiB

Joker

///In the name of GOD
//#pragma GCC optimize("O2")
#include<bits/stdc++.h>
#define Mp make_pair
using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;
const ll MXN = 2e5 + 10;
ll n, m, q;
ll Par[MXN], Sz[MXN], xr[MXN];
ll from[MXN], to[MXN], dp[MXN];
bool bip = true;
vector<pll> hist;
pll Find(ll x){
    if(Par[x] == x) return Mp(x, xr[x]);
    pll nw = Find(Par[x]);
    nw.second ^=  xr[x];
    return nw;
}
void Union(ll x, ll y){
    pll X = Find(x), Y = Find(y);
    if(X.first == Y.first){
        hist.push_back({-1, bip});
        if(X.second == Y.second) bip = 0;
        return;
    }
    if(Sz[X.first] < Sz[Y.first]) swap(X, Y);
    xr[Y.first] = 1LL ^ X.second ^ Y.second;
    Par[Y.first] = X.first, Sz[X.first] += Sz[Y.first];
    hist.push_back({X.first, Y.first});
}
void Undo(){
    ll x, y; tie(x, y) = hist.back(); hist.pop_back();
    if(x == -1){
        bip = y; return;
    }
    xr[y] = 0, Par[y] = y, Sz[x] -= Sz[y];
}
inline void add_edge(ll i){
    Union(from[i], to[i]);
}
void solve(ll l, ll r, ll opl, ll opr){ // [1, l - 1] + [opr + 1, m]
    if(r < l) return;
    ll mid = (l + r) / 2, opt = -1, tun = 0;
    dp[mid] = m + 1;
    for(int i = l; i < mid; i ++) add_edge(i), tun ++;
    for(int i = opr; i >= max(opl, mid); i --) add_edge(i), tun ++;
    if(bip) dp[mid] = max(opl, mid) - 1;
    else{
        for(int i = max(opl, mid); i <= opr; i ++){
            Undo(); tun --;
            if(bip){
                dp[mid] = i;
                while(tun) Undo(), tun --;
                break;
            }
        }
    }
    opt = min(dp[mid], m);
    while(tun) Undo(), tun --;
    for(int i = l; i <= mid; i ++) add_edge(i), tun ++;
    solve(mid + 1, r, opt, opr);
    while(tun) Undo(), tun --;
    for(int i = opt + 1; i <= opr; i ++) add_edge(i), tun ++;
    solve(l, mid - 1, opl, opt);
    while(tun) Undo(), tun --;
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
    cin >> n >> m >> q;
    for(int i = 1; i <= n; i ++) Par[i] = i, Sz[i] = 1;
    for(int i = 1; i <= m; i ++) cin >> from[i] >> to[i];
    solve(1, m, 1, m);
    while(q --){
        ll l, r; cin >> l >> r;
        cout << (dp[l] <= r ? "NO" : "YES") << '\n';
    }
    return 0;
}
/*!
    HE'S AN INSTIGATOR,
    ENEMY ELIMINATOR,
    AND WHEN HE KNOCKS YOU BETTER
    YOU BETTER LET HIM IN.
*/
//! N.N

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