Submission #725587

#	Time	Username	Problem	Language	Result	Execution time	Memory
725587		bitaro1337	Joker (BOI20_joker)	C++14	0 / 100	209 ms	7260 KiB

Joker

//BITARO BITARO BITARO
#include <bits/stdc++.h>
using namespace std;
 
const int N = 2e5 + 5;
pair<int, int> p[N];
int s[N], eu[N], ev[N],  pos[N];
stack<pair<int, int>> st;
pair<int, int> get(int u) {
    if(p[u].first == u) return p[u];
    pair<int, int> x = get(p[u].first);
    return make_pair(x.first, x.second ^ p[u].second);
}
 
int bip_all = 1;
void uni(int a, int b) {
    if(a == b) return;
    pair<int, int> A = get(a), B = get(b);
    a = A.first, b = B.first;
    int para = A.second, parb = B.second;
    if(a == b) {
        if(para == parb) {
            bip_all = 0;
        }
    } else {
        if(s[a] >= s[b]) swap(a, b);
        st.push(p[a]);
        p[a] = make_pair(b, para ^ parb ^ 1);
        s[b] += s[a];
    }
}
void rollback(int SIZE) {
    while(st.size() > SIZE) {
        pair<int, int> a = st.top();
        pair<int, int> b = get(a.first);
        p[a.first].first = a.first;
        p[a.first].second ^= b.second ^ 1;
        s[b.first] -= s[a.first];
        st.pop();
    }
}
 
void rec(int l1, int l2, int r1, int r2) {
    if(l1 > l2) return;
    int initial_state = st.size(), initial_bip = bip_all;
    int lm = l1 + l2 >> 1;
    for(int i = l1; i < lm; ++i) uni(eu[i], ev[i]);
    int rans = r2;
    for(int i = r2; i >= r1; --i) {
        uni(eu[i], ev[i]);
        if(!bip_all) {
            rans = i; 
            break;
        }
    }
    pos[lm] = rans;
    rollback(initial_state);
    bip_all = initial_bip;
    
    for(int i = r2; i >= rans; --i) uni(eu[i], ev[i]);
    rec(l1, lm - 1, r1, rans);

    bip_all = initial_bip;
    rollback(initial_state);
 
    for(int i = l1; i <= lm; ++i) uni(eu[i], ev[i]);
    rec(lm + 1, l2, rans, r2);
    
    rollback(initial_state);
    bip_all = initial_bip;
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, m, q; cin >> n >> m >> q;
    for(int i = 0; i <= n; ++i) {
        p[i].first = i, p[i].second = 0, s[i] = 1;
    }
    for(int i = 1; i <= m; ++i) cin >> eu[i] >> ev[i], pos[i] = -1;
    for(int i = 1; i <= m; ++i) {
        uni(eu[i], ev[i]);
    }
    if(bip_all) {
        while(q--) {
            int l, r; cin >> l >> r;
            cout << "NO\n";
        }
        return 0;
    }
    rollback(0);
    bip_all = 1;
    rec(1, m, 1, m + 1);
    for(int i = 1; i <= m; ++i) {
        assert(pos[i] != -1);
    }
    while(q--) {
        int l, r; cin >> l >> r;
        if(pos[l] > r) {
            cout << "YES\n";
        } else {
            cout << "NO\n";
        }
    }
}

Compilation message (stderr)

Joker.cpp: In function 'void rollback(int)':
Joker.cpp:33:21: warning: comparison of integer expressions of different signedness: 'std::stack<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   33 |     while(st.size() > SIZE) {
      |           ~~~~~~~~~~^~~~~~
Joker.cpp: In function 'void rec(int, int, int, int)':
Joker.cpp:46:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   46 |     int lm = l1 + l2 >> 1;
      |              ~~~^~~~

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