oj.uz

Submission #256105

# Submission time Handle Problem Language Result Execution time Memory
256105 2020-08-02T09:49:49 Z 문홍윤(#5033) Joker (BOI20_joker) C++17
25 / 100
 398 ms 8168 KB 
#include <bits/stdc++.h>
#define pb emplace_back
#define mp make_pair
#define F first
#define S second
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;

struct UNION_FIND{
    int par[400010], sz[400010];
    vector<int> vc;
    UNION_FIND(){for(int i=1; i<=400000; i++)par[i]=i, sz[i]=1;}
    int findpar(int num){return num==par[num]?num:findpar(par[num]);}
    void mergepar(int a, int b){
        a=findpar(a);
        b=findpar(b);
        if(a==b)return;
        if(sz[a]<sz[b])swap(a, b);
        vc.pb(b);
        par[b]=a;
        sz[a]+=sz[b];
    }
    void rollback(){
        int tmp=vc.back();
        vc.pop_back();
        sz[par[tmp]]-=sz[tmp];
        par[tmp]=tmp;
    }
}uf;

int n, m, q, ans[200010], l, r;
pii edg[200010];

int link(int a, int b){
    uf.mergepar(2*a-1, 2*b);
    uf.mergepar(2*a, 2*b-1);
    if(uf.findpar(2*a)==uf.findpar(2*a-1))return 1;
    return 0;
}

void dnc(int sa, int ea, int sb, int eb){
    if(sa>ea)return;
    int mid=(sa+ea)/2;
    int tmp1=uf.vc.size();
    int flg=0;
    for(int i=l+1; i<=mid; i++)flg=max(flg, link(edg[i].F, edg[i].S));
    l=mid;
    int tmp2=uf.vc.size();
    if(!flg){
        for(int i=r-1; i>l&&i>=sb; i--){
            int sz=uf.vc.size();
            int tmp=link(edg[i].F, edg[i].S);
            if(tmp){
                while(sz<uf.vc.size())uf.rollback();
                r=i+1;
                break;
            }
        }
    }
    ans[mid]=r;
    while(tmp2<uf.vc.size())uf.rollback();
    r=eb;
    link(edg[mid+1].F, edg[mid+1].S);
    l=mid+1;
    dnc(mid+1, ea, ans[mid], eb);
    while(tmp1<uf.vc.size())uf.rollback();
    l=sa;
    for(int i=r-1; i>=ans[mid]; i--)link(edg[i].F, edg[i].S);
    r=ans[mid];
    dnc(sa, mid-1, sb, ans[mid]);
    while(tmp1<uf.vc.size())uf.rollback();
    r=eb;
}

int main(){
    scanf("%d %d %d", &n, &m, &q);
    int np=0;
    for(int i=1; i<=m; i++){
        scanf("%d %d", &edg[i].F, &edg[i].S);
        np=max(np, link(edg[i].F, edg[i].S));
    }
    while(uf.vc.size()>0)uf.rollback();
    r=m+1;
    if(np)dnc(0, m, 1, m+1);
    //for(int i=0; i<=m; i++)printf("! %d : %d\n", i, ans[i]);
    for(int i=1; i<=q; i++){
        int a, b;
        scanf("%d %d", &a, &b);
        if(!np)puts("NO");
        else if(ans[a-1]<=b+1)puts("NO");
        else puts("YES");
    }
}

Compilation message

Joker.cpp: In function 'void dnc(int, int, int, int)':
Joker.cpp:55:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 while(sz<uf.vc.size())uf.rollback();
                       ~~^~~~~~~~~~~~~
Joker.cpp:62:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(tmp2<uf.vc.size())uf.rollback();
           ~~~~^~~~~~~~~~~~~
Joker.cpp:67:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(tmp1<uf.vc.size())uf.rollback();
           ~~~~^~~~~~~~~~~~~
Joker.cpp:72:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(tmp1<uf.vc.size())uf.rollback();
           ~~~~^~~~~~~~~~~~~
Joker.cpp: In function 'int main()':
Joker.cpp:77: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:80:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &edg[i].F, &edg[i].S);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Joker.cpp:89:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &a, &b);
         ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 6.0

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

Subtask #2
0 / 8.0

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

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3456 KB Output is correct
2 Correct 2 ms 3456 KB Output is correct
3 Correct 278 ms 7400 KB Output is correct
4 Correct 129 ms 7268 KB Output is correct
5 Correct 291 ms 8124 KB Output is correct
6 Correct 326 ms 7404 KB Output is correct
7 Correct 317 ms 7532 KB Output is correct
8 Correct 271 ms 7152 KB Output is correct
9 Correct 336 ms 7532 KB Output is correct
10 Correct 382 ms 8168 KB Output is correct
11 Correct 268 ms 7404 KB Output is correct
12 Correct 326 ms 7780 KB Output is correct
13 Correct 254 ms 6772 KB Output is correct
14 Correct 280 ms 7128 KB Output is correct
15 Correct 370 ms 7524 KB Output is correct
16 Correct 398 ms 7908 KB Output is correct

Subtask #4
0 / 10.0

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

Subtask #5
0 / 22.0

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

Subtask #6
0 / 29.0

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