oj.uz

Submission #256107

# Submission time Handle Problem Language Result Execution time Memory
256107 2020-08-02T09:53:53 Z 반딧불(#5032) Joker (BOI20_joker) C++17
0 / 100
 146 ms 262148 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];

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

pair<int, int> find(int x){
    if(x == par[x].first) return par[x];
    bool tmp = par[x].second;
    parRev[pnt].push(make_pair(x, par[x]));
    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);

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

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

void recal(){
    while(!parRev[pnt].empty()){
        auto tmp = parRev[pnt].top();
        par[tmp.first] = tmp.second;
        parRev[pnt].pop();
    }
    while(!szRev[pnt].empty()){
        auto tmp = szRev[pnt].top();
        sz[tmp.first] = tmp.second;
        szRev[pnt].pop();
    }
}

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;

    pnt = m;
    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;

    recal();

    for(int j=val+1; j<=e; j++){
        int x1 = edgeX[j];
        int x2 = edgeY[j];
        merge(x1, x2);
    }
    calculate(l, m-1, s, val);
    pnt = m;
    recal();

    for(int j=l; j<=m; j++){
        int x1 = edgeX[j];
        int x2 = edgeY[j];
        merge(x1, x2);
    }
    calculate(m+1, r, val, e);
    pnt = m;
    recal();
}

int main(){
    bool chk = 0;
    scanf("%d %d %d", &n, &m, &q);
    for(int i=1; i<=n; i++) par[i] = make_pair(i, 0), sz[i] = 0;

    for(int i=1; i<=m; i++){
        int s, e;
        scanf("%d %d", &s, &e);
        edgeX[i] = s, edgeY[i] = e;
        if(!merge(s, e)) chk = 1;
    }
    if(!chk){
        for(int i=1; i<=q; i++) printf("NO\n");
        return 0;
    }

    recal();

    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:116: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:121: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:135: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 Runtime error 146 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 146 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 146 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 146 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 22.0

# Verdict Execution time Memory Grader output
1 Runtime error 146 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# Verdict Execution time Memory Grader output
1 Runtime error 146 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -