oj.uz

Submission #256055

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

using namespace std;

typedef long long ll;

struct dat{
    int s, e, i;
    dat(){}
    dat(int s, int e, int i): s(s), e(e), i(i){}
};
vector<dat> link[200002];

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

    x = par[x].first, y = par[y].first;
    if(sz[x] < sz[y]) swap(x, y);
    par[y] = make_pair(x, par[x].second ^ par[y].second ^ 1);
    if(sz[x] == sz[y]) x++;
    return true;
}

bool dfs(int x, int y = 1){
    chk[x] = y;
    for(auto &nxt: link[x]){
        if(l <= nxt.i && nxt.i <= r) continue;
        if(chk[nxt.e] == y) return true;
        if(chk[nxt.e] == 0 && dfs(nxt.e, 3-y)) return true;
    }
    return false;
}

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

    for(int i=1; i<=200 && i<=m; i++){
        for(int j=1; j<=n; j++) par[j] = make_pair(j, 0), sz[j] = 1;
        for(int j=1; j<i; j++){
            int s = edgeX[j];
            int e = edgeY[j];

            if(!merge(s, e)){
                minNeeded[i] = 1e9;
                break;
            }
        }

        for(int j=m; j>i; j--){
            int s = edgeX[j];
            int e = edgeY[j];

            if(!merge(s, e)){
                minNeeded[i] = j;
                break;
            }
        }
    }

    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:56: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:59: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:89: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 3 ms 4992 KB Output is correct
2 Correct 3 ms 4992 KB Output is correct
3 Correct 3 ms 4992 KB Output is correct
4 Incorrect 3 ms 4992 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

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

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4992 KB Output is correct
2 Correct 3 ms 4992 KB Output is correct
3 Correct 520 ms 15352 KB Output is correct
4 Correct 1114 ms 17912 KB Output is correct
5 Incorrect 318 ms 17660 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

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

Subtask #5
0 / 22.0

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

Subtask #6
0 / 29.0

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