oj.uz

답안 #725599

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
725599 2023-04-17T17:51:32 Z bitaro1337 Joker (BOI20_joker) C++14
0 / 100
 232 ms 7244 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 = 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 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);
        bip_all = initial_bip;
        rollback(initial_state);
    }
    
    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:47:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   47 |     int lm = l1 + l2 >> 1;
      |              ~~~^~~~

Subtask #1
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Runtime error 1 ms 468 KB Execution killed with signal 6
6 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Runtime error 1 ms 468 KB Execution killed with signal 6
6 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 170 ms 5284 KB Output is correct
4 Correct 65 ms 7244 KB Output is correct
5 Incorrect 232 ms 6872 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Runtime error 1 ms 468 KB Execution killed with signal 6
6 Halted 0 ms 0 KB -

Subtask #5
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Runtime error 1 ms 468 KB Execution killed with signal 6
6 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Runtime error 1 ms 468 KB Execution killed with signal 6
6 Halted 0 ms 0 KB -