oj.uz

답안 #725605

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
725605 2023-04-17T18:01:15 Z bitaro1337 Joker (BOI20_joker) C++14
25 / 100
 622 ms 7216 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);
            swap(A, B);
        }
        st.push(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];
        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:36: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]
   36 |     while(st.size() > SIZE) {
      |           ~~~~~~~~~~^~~~~~
Joker.cpp: In function 'void rec(int, int, int)':
Joker.cpp:50:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   50 |     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 0 ms 340 KB Output is correct
4 Correct 1 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 0 ms 340 KB Output is correct
4 Correct 1 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
25.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 188 ms 5328 KB Output is correct
4 Correct 78 ms 7216 KB Output is correct
5 Correct 222 ms 6792 KB Output is correct
6 Correct 201 ms 5072 KB Output is correct
7 Correct 239 ms 4976 KB Output is correct
8 Correct 210 ms 4636 KB Output is correct
9 Correct 254 ms 5456 KB Output is correct
10 Correct 342 ms 7128 KB Output is correct
11 Correct 622 ms 5252 KB Output is correct
12 Correct 533 ms 6676 KB Output is correct
13 Correct 199 ms 3580 KB Output is correct
14 Correct 233 ms 4380 KB Output is correct
15 Correct 311 ms 6004 KB Output is correct
16 Correct 349 ms 6968 KB Output is correct

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 0 ms 340 KB Output is correct
4 Correct 1 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 0 ms 340 KB Output is correct
4 Correct 1 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 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Runtime error 1 ms 468 KB Execution killed with signal 6
6 Halted 0 ms 0 KB -