oj.uz

Submission #1100817

# Submission time Handle Problem Language Result Execution time Memory
1100817 2024-10-14T18:41:29 Z vivkostov Joker (BOI20_joker) C++14
25 / 100
 171 ms 7640 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(mid-l1+1);

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

    for(int i=r2-1;i>=otg[mid];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;
}

Compilation message

Joker.cpp: In function 'void rec(int, int, int, int)':
Joker.cpp:79:9: warning: unused variable 'nbr' [-Wunused-variable]
   79 |     int nbr=br;
      |         ^~~

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 94 ms 6592 KB Output is correct
4 Correct 164 ms 7476 KB Output is correct
5 Correct 82 ms 7484 KB Output is correct
6 Correct 107 ms 6796 KB Output is correct
7 Correct 109 ms 6804 KB Output is correct
8 Correct 121 ms 6576 KB Output is correct
9 Correct 129 ms 6820 KB Output is correct
10 Correct 163 ms 7632 KB Output is correct
11 Correct 124 ms 6812 KB Output is correct
12 Correct 150 ms 7500 KB Output is correct
13 Correct 123 ms 5960 KB Output is correct
14 Correct 119 ms 6312 KB Output is correct
15 Correct 161 ms 6932 KB Output is correct
16 Correct 171 ms 7640 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 -