oj.uz

Submission #1100806

# Submission time Handle Problem Language Result Execution time Memory
1100806 2024-10-14T18:32:24 Z vivkostov Joker (BOI20_joker) C++14
25 / 100
 166 ms 7656 KB 
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}
struct cell
{
    int a,b,tim;
};
int n,m,q,a[200005],b[200005],l,r,lead[200005],sw[200005],sz[200005],lamp,otg[200005],br;
stack<cell>s;
void prec()
{
    for(int i=1;i<=n;i++)
    {
        lead[i]=i;
        sz[i]=1;
        sw[i]=0;
    }
}
int get_lead(int beg)
{
    if(lead[beg]==beg)return beg;
    return get_lead(lead[beg]);
}
int get_br(int beg,int br)
{
    if(lead[beg]==beg)return br;
    return get_br(lead[beg],br+sw[beg]);
}
void add(int a,int b)
{
    br++;
    int la=get_lead(a);
    int lb=get_lead(b);
    if(la==lb)
    {
        if(get_br(a,0)%2==get_br(b,0)%2)lamp=br;
        return;
    }
    if(sz[la]<sz[lb])
    {
        swap(la,lb);
        swap(a,b);
    }
    lead[lb]=la;
    sz[la]+=sz[lb];
    if(get_br(a,0)%2==get_br(b,0)%2)sw[lb]++;
    cell h;
    h.a=la;
    h.b=lb;
    h.tim=br;
    s.push(h);
}
void rem(int num)
{
    for(int i=1;i<=num;i++)
    {
        if(s.top().tim==br)
        {
            int a=s.top().a;
            int b=s.top().b;
            s.pop();
            sz[a]-=sz[b];
            lead[b]=b;
        }
        br--;
        if(br<lamp)lamp=0;
    }
}
void rec(int l1,int l2,int r1,int r2)
{
    if(l1>l2)return;
    int mid=(l1+l2)/2;
    int nbr=br;
    for(int i=l1;i<mid;i++)
    {
        add(a[i],b[i]);
    }
    //cout<<br<<endl;
    int x=r2;
    int obr=br;
    while(!lamp&&x>max(mid,r1))
    {
        x--;
        add(a[x],b[x]);
    }
    int ubr=br;
    otg[mid]=x;
    //cout<<l1<<" "<<l2<<" "<<r1<<" "<<r2<<" "<<otg[mid]<<endl;
    //cout<<nbr<<" "<<obr<<" "<<br<<" "<<mid<<endl;
    rem(ubr-obr);

    add(a[mid],b[mid]);

    rec(mid+1,l2,otg[mid],r2);

    rem(1);

    //cout<<l1<<" "<<l2<<" "<<br<<" "<<nbr<<" "<<obr<<" "<<ubr<<" "<<otg[mid]<<endl;

    rem(obr-nbr);

    for(int i=r2-(ubr-obr);i<r2;i++)
    {
        add(a[i],b[i]);
    }

    rec(l1,mid-1,r1,otg[mid]);

    rem(ubr-obr);
}
void read()
{
    cin>>n>>m>>q;
    prec();
    for(int i=1;i<=m;i++)
    {
        cin>>a[i]>>b[i];
    }
    rec(1,m,1,m+1);
    for(int i=1;i<=q;i++)
    {
        cin>>l>>r;
        if(otg[l]>r)cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
}
int main()
{
    speed();
    read();
    return 0;
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4432 KB Output is correct
2 Correct 1 ms 4432 KB Output is correct
3 Correct 1 ms 4432 KB Output is correct
4 Incorrect 1 ms 4432 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 4432 KB Output is correct
2 Correct 1 ms 4432 KB Output is correct
3 Correct 1 ms 4432 KB Output is correct
4 Incorrect 1 ms 4432 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 1 ms 4432 KB Output is correct
2 Correct 1 ms 4432 KB Output is correct
3 Correct 99 ms 6588 KB Output is correct
4 Correct 158 ms 7632 KB Output is correct
5 Correct 82 ms 7484 KB Output is correct
6 Correct 112 ms 6784 KB Output is correct
7 Correct 109 ms 6796 KB Output is correct
8 Correct 117 ms 6580 KB Output is correct
9 Correct 131 ms 6944 KB Output is correct
10 Correct 165 ms 7628 KB Output is correct
11 Correct 126 ms 6744 KB Output is correct
12 Correct 139 ms 7488 KB Output is correct
13 Correct 126 ms 5844 KB Output is correct
14 Correct 128 ms 6332 KB Output is correct
15 Correct 163 ms 6928 KB Output is correct
16 Correct 166 ms 7656 KB Output is correct

Subtask #4
0 / 10.0

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