oj.uz

Submission #256086

# Submission time Handle Problem Language Result Execution time Memory
256086 2020-08-02T09:40:10 Z 반딧불(#5032) Joker (BOI20_joker) C++17
0 / 100
 62 ms 4144 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")

using namespace std;

typedef long long ll;

int n, m, q;
int l, r;
int edgeX[200002], edgeY[200002];

int chk[200002];
int minNeeded[2002];

pair<int, bool> par[200002];
int sz[200002];

bool parCng[200002], szCng[200002];
stack<pair<int, pair<int, bool> > > parRev;
stack<pair<int, int> > szRev;

pair<int, int> find(int x){
    if(x == par[x].first) return par[x];
    bool tmp = par[x].second;
    if(!parCng[x]) parRev.push(make_pair(x, par[x])), parCng[x] = 1;
    par[x] = find(par[x].first);
    par[x].second ^= tmp;
    return par[x];
}

bool merge(int x, int y){
    pair<int, int> px = find(x), py = find(y);
    if(px.first == py.first && px.second == py.second) return false;
    if(px.first == py.first) return true;

    int xx = par[x].second, yy = par[y].second;
    x = par[x].first, y = par[y].first;
    if(sz[x] < sz[y]) swap(x, y);

    if(!parCng[y]) parRev.push(make_pair(y, par[y])), parCng[y] = 1;
    par[y] = make_pair(x, xx ^ yy ^ 1);

    if(!szCng[x]) szRev.push(make_pair(x, sz[x])), szCng[x] = 1;
    if(sz[x] == sz[y]) sz[x]++;
    return true;
}

void calculate(int l, int r, int s, int e){
    if(l>r) return;
    if(l == 1e9){
        for(int i=l; i<=r; i++) minNeeded[i] = 1e9;
        return;
    }
    int val = s-1;

    int m = (l+r)>>1;

    for(int j=l; j<m; j++){
        int x1 = edgeX[j];
        int x2 = edgeY[j];
        if(!merge(x1, x2)){
            val = 1e9;
            break;
        }
    }

    for(int j=e; j>s; j--){
        int x1 = edgeX[j];
        int x2 = edgeY[j];
        if(!merge(x1, x2)){
            val = j-1;
            break;
        }
    }
    minNeeded[m] = val;
    if(l==r) return;

    while(!parRev.empty()){
        auto tmp = parRev.top();
        par[tmp.first] = tmp.second;
        parCng[tmp.first] = 0;
        parRev.pop();
    }
    while(!szRev.empty()){
        auto tmp = szRev.top();
        sz[tmp.first] = tmp.second;
        szCng[tmp.first] = 0;
        szRev.pop();
    }

    calculate(l, m-1, s, val);
    calculate(m+1, r, val, e);
}

int main(){
    scanf("%d %d %d", &n, &m, &q);
    for(int i=1; i<=m; i++){
        int s, e;
        scanf("%d %d", &s, &e);
        edgeX[i] = s, edgeY[i] = e;
    }

    calculate(1, m, 1, m);

    while(q--){
        scanf("%d %d", &l, &r);
        printf("%s\n", minNeeded[l] >= r ? "YES" : "NO");
    }
}

Compilation message

Joker.cpp: In function 'int main()':
Joker.cpp:97:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d", &n, &m, &q);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Joker.cpp:100:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &s, &e);
         ~~~~~^~~~~~~~~~~~~~~~~
Joker.cpp:107:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &l, &r);
         ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Incorrect 0 ms 384 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 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Incorrect 0 ms 384 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 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Runtime error 62 ms 4144 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Incorrect 0 ms 384 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 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Incorrect 0 ms 384 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 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Incorrect 0 ms 384 KB Output isn't correct
5 Halted 0 ms 0 KB -