Submission #725607

#	Time	Username	Problem	Language	Result	Execution time	Memory
725607		bitaro1337	Joker (BOI20_joker)	C++14	100 / 100	343 ms	14220 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<pair<int, int>, 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[b]});
        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().first;
        pair<int, int> b = st.top().second;
        pair<int, int> B = p[a.first];
        s[b.first] -= s[a.first];
        p[a.first].first = a.first;
        p[a.first].second = a.second;
        st.pop();
    }
}
 
void rec(int l1, int l2, int r2) {
    assert(l1 <= l2);
    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;
    if(bip_all) {
        for(int i = r2 - 1; i >= lm; --i) {
            uni(eu[i], ev[i]);
            if(!bip_all) {
                rans = i; 
                break;
            }
        }
    }

    assert(!bip_all);
    pos[lm] = rans;

    rollback(initial_state);
    bip_all = initial_bip;
    
    if(l1 <= lm - 1) {
        for(int i = r2 - 1; i >= rans; --i) uni(eu[i], ev[i]);
        rec(l1, lm - 1, rans);

        rollback(initial_state);
        bip_all = initial_bip;
    }
    
    if(lm + 1 <= l2) {
        for(int i = l1; i <= lm - (r2 == lm); ++i) uni(eu[i], ev[i]);
        rec(lm + 1, l2, 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, 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<std::pair<int, int>, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   33 |     while(st.size() > SIZE) {
      |           ~~~~~~~~~~^~~~~~
Joker.cpp:36:24: warning: variable 'B' set but not used [-Wunused-but-set-variable]
   36 |         pair<int, int> B = p[a.first];
      |                        ^
Joker.cpp: In function 'void rec(int, int, int)':
Joker.cpp:48:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   48 |     int lm = l1 + l2 >> 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