oj.uz

Submission #1100818

# Submission time Handle Problem Language Result Execution time Memory
1100818 2024-10-14T18:42:05 Z vivkostov Joker (BOI20_joker) C++14
25 / 100
 164 ms 7660 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(r2-otg[mid]);
}
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 6608 KB Output is correct
4 Correct 159 ms 7472 KB Output is correct
5 Correct 83 ms 7484 KB Output is correct
6 Correct 108 ms 6796 KB Output is correct
7 Correct 116 ms 6796 KB Output is correct
8 Correct 115 ms 6572 KB Output is correct
9 Correct 143 ms 6820 KB Output is correct
10 Correct 158 ms 7640 KB Output is correct
11 Correct 124 ms 6744 KB Output is correct
12 Correct 152 ms 7488 KB Output is correct
13 Correct 127 ms 5984 KB Output is correct
14 Correct 125 ms 6332 KB Output is correct
15 Correct 162 ms 6940 KB Output is correct
16 Correct 164 ms 7660 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 -