Submission #1100582

#	Time	Username	Problem	Language	Result	Execution time	Memory
1100582		vivkostov	Joker (BOI20_joker)	C++14	14 / 100	2071 ms	5076 KiB

Joker

#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;
};
int n,m,q,a[200005],b[200005],l,r,lead[200005],sw[200005],sz[200005],lamp;
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)
{
    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=1;
        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;
    s.push(h);
}
void rem()
{
    int a=s.top().a;
    int b=s.top().b;
    s.pop();
    sz[a]-=sz[b];
    lead[b]=b;
}
void read()
{
    cin>>n>>m>>q;
    prec();
    for(int i=1;i<=m;i++)
    {
        cin>>a[i]>>b[i];
    }
    for(int i=1;i<=q;i++)
    {
        cin>>l>>r;
        for(int j=1;j<l;j++)
        {
            add(a[j],b[j]);
        }
        for(int j=r+1;j<=m;j++)
        {
            add(a[j],b[j]);
        }
        if(lamp)cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
        while(!s.empty())rem();
        lamp=0;
    }
}
int main()
{
    speed();
    read();
    return 0;
}

• Subtask 1: 6 / 6
• Subtask 2: 8 / 8
• Subtask 3: 0 / 25
• Subtask 4: 0 / 10
• Subtask 5: 0 / 22
• Subtask 6: 0 / 29