oj.uz

Submission #725602

# Submission time Handle Problem Language Result Execution time Memory
725602 2023-04-17T17:58:38 Z bitaro1337 Joker (BOI20_joker) C++14
25 / 100
 603 ms 7236 KB 
//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 = p[a.first];
        assert(p[a.first].first != 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 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

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)':
Joker.cpp:48:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   48 |     int lm = l1 + l2 >> 1;
      |              ~~~^~~~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Incorrect 0 ms 340 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Incorrect 0 ms 340 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 189 ms 5312 KB Output is correct
4 Correct 63 ms 7236 KB Output is correct
5 Correct 189 ms 7036 KB Output is correct
6 Correct 201 ms 4984 KB Output is correct
7 Correct 207 ms 4964 KB Output is correct
8 Correct 219 ms 4556 KB Output is correct
9 Correct 268 ms 5348 KB Output is correct
10 Correct 350 ms 7120 KB Output is correct
11 Correct 603 ms 5244 KB Output is correct
12 Correct 511 ms 6708 KB Output is correct
13 Correct 190 ms 3572 KB Output is correct
14 Correct 214 ms 4380 KB Output is correct
15 Correct 306 ms 5936 KB Output is correct
16 Correct 347 ms 6964 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Incorrect 0 ms 340 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Incorrect 0 ms 340 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Incorrect 0 ms 340 KB Output isn't correct
6 Halted 0 ms 0 KB -