Submission #529280

#	Time	Username	Problem	Language	Result	Execution time	Memory
529280		Saacoota	Joker (BOI20_joker)	C++14	100 / 100	198 ms	13800 KiB

Joker

#include <bits/stdc++.h>
#define fi first
#define se second
#define ii pair < int , int >

using namespace std;

const int maxn = 3e5 + 10;

struct node {
    int u , v , pu , pv;
    node(){}
    node(int u,int pu,int v,int pv):
    u(u) , v(v) , pu(pu) , pv(pv){}
};
vector < node > indsu;
int par[maxn] , c[maxn] , last[maxn] , u[maxn] , v[maxn] , n , m , q;

ii fin(int u) {
    int color = 0;
    while (par[u] > 0) {
        color ^= c[u];
        u = par[u];
    }
    return ii(u , color);
}

bool push(int u,int v) {
    ii x = fin(u);
    ii y = fin(v);
    if (x.fi == y.fi) return (x.se != y.se);
    indsu.emplace_back(x.fi , par[x.fi] , y.fi , par[y.fi]);
    if (par[x.fi] > par[y.fi]) swap(x , y);
    par[x.fi] += par[y.fi];
    par[y.fi] = x.fi;
    c[y.fi] = x.se ^ y.se ^ 1;
    return true;
}

void roll(int stp) {
    while (indsu.size() > stp) {
        node x = indsu.back();
        indsu.pop_back();
        par[x.u] = x.pu;
        par[x.v] = x.pv;
    }
}

void cal(int l,int r,int optl,int optr) {
    if (l > r || optl > optr) return;
    int mid = l + r >> 1;
    int cur = indsu.size();
    bool ok = true;
    for (int i = l ; i < mid ; ++i)
    ok &= push(u[i] , v[i]);
    if (ok) {
        int crr = indsu.size();
        last[mid] = optl;
        for (int i = min(optr , m) ; i >= max(optl , mid) ; --i) {
            if (!push(u[i] , v[i])) {
                last[mid] = i;
                break;
            }
        }
        roll(crr);
        if (push(u[mid] , v[mid])) cal(mid + 1 , r , last[mid] , optr);
    }
    roll(cur);
    for (int i = last[mid] + 1 ; i <= optr ; ++i) push(u[i] , v[i]);
    cal(l , mid - 1 , optl , last[mid]);
    roll(cur);
}

int main() {
//    freopen("nohome.inp","r",stdin);
//    freopen("nohome.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m >> q;
    for (int i = 1 ; i <= m ; ++i) {
        cin >> u[i] >> v[i];
        last[i] = m + 1;
    }
    memset(par,-1,sizeof(par));
    cal(1 , m , 1 , m + 1);
    while (q--) {
        int l , r;
        cin >> l >> r;
        if (r >= last[l]) cout << "NO\n";
        else cout << "YES\n";
    }
}

Compilation message (stderr)

Joker.cpp: In function 'void roll(int)':
Joker.cpp:41:25: warning: comparison of integer expressions of different signedness: 'std::vector<node>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   41 |     while (indsu.size() > stp) {
      |            ~~~~~~~~~~~~~^~~~~
Joker.cpp: In function 'void cal(int, int, int, int)':
Joker.cpp:51:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   51 |     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