oj.uz

Submission #877214

# Submission time Handle Problem Language Result Execution time Memory
877214 2023-11-23T03:56:35 Z socpite Joker (BOI20_joker) C++14
0 / 100
 231 ms 14120 KB 
#include <bits/stdc++.h>
using namespace std;

const int maxn = 5e5 + 5;

int up[maxn], par[maxn];

int n, m, q;

int Find(int x){
    if(!up[x])return x;
    else{
        int tmp = up[x];
        up[x] = Find(tmp);
        par[x]^=par[tmp];
        return up[x];
    }
}

bool bad = 0;

vector<int> undo;

void Union(int a, int b){
    undo.push_back(a);
    undo.push_back(b);
    int ra = Find(a), rb = Find(b);
    if(ra == rb){
        // cout << ra << endl;
        // cout << par[a] << " " << par[b] << endl;
        if(par[a] == par[b])bad = 1;
    }
    else{
        up[rb]= ra;
        par[rb]^=par[a]^par[b]^1;
    }
}

void rs() {
    bad = 0;
    for(auto v: undo)up[v] = par[v] = 0;
    undo.clear();
}

int U[maxn], V[maxn];
int bound[maxn];

void dnc(int l, int r, int ql, int qr) {
    if(l > r)return;
    int mid = (l+r)>>1;
    // cout << mid << " " << ql << " " << qr << endl;
    rs();
    int ans = qr;
    if(ql < mid){
        for(int i = mid; i < ql; i++)Union(U[i], V[i]);
    }
    for(int i = max(mid, ql); i < qr; i++){
        Union(U[i], V[i]);
        if(bad){
            ans = i;
            break;
        }
    }
    // cout << ans << endl;
    bound[mid] = ans;
    dnc(l, mid-1, ql, ans);
    dnc(mid+1, r, ans, qr);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m >> q;
    for(int i = 1; i <= m; i++)cin >> U[i] >> V[i];
    for(int i = m+1; i <= 2*m; i++){
        U[i] = U[i-m];
        V[i] = V[i-m];
    }
    dnc(1, 2*m, 1, 2*m+1);
    // for(int i = 1; i <= 2*m; i++)cout << i << " " << bound[i] << endl;
    while(q--){
        int l, r;
        cin >> l >> r;
        if(l + m - 1 >= bound[r+1])cout << "YES";
        else cout << "NO";
        cout << "\n";
    }
}

Subtask #1
0 / 6.0

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

Subtask #2
0 / 8.0

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

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 148 ms 9492 KB Output is correct
4 Correct 231 ms 12580 KB Output is correct
5 Incorrect 226 ms 14120 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

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

Subtask #5
0 / 22.0

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

Subtask #6
0 / 29.0

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