oj.uz

Submission #1100813

# Submission time Handle Problem Language Result Execution time Memory
1100813 2024-10-14T18:36:34 Z vivkostov Joker (BOI20_joker) C++14
25 / 100
 205 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-(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;
}

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 4604 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 4604 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 4604 KB Output is correct
2 Correct 1 ms 4432 KB Output is correct
3 Correct 113 ms 6612 KB Output is correct
4 Correct 172 ms 7468 KB Output is correct
5 Correct 89 ms 7660 KB Output is correct
6 Correct 112 ms 6796 KB Output is correct
7 Correct 109 ms 6796 KB Output is correct
8 Correct 127 ms 6460 KB Output is correct
9 Correct 132 ms 6812 KB Output is correct
10 Correct 162 ms 7656 KB Output is correct
11 Correct 124 ms 6812 KB Output is correct
12 Correct 146 ms 7488 KB Output is correct
13 Correct 125 ms 5960 KB Output is correct
14 Correct 127 ms 6332 KB Output is correct
15 Correct 205 ms 6936 KB Output is correct
16 Correct 172 ms 7476 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4604 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 4604 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 4604 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 -