Submission #1095162

#	Time	Username	Problem	Language	Result	Execution time	Memory
1095162		simona1230	Joker (BOI20_joker)	C++17	71 / 100	1429 ms	17980 KiB

Joker

#include <bits/stdc++.h>

using namespace std;
struct query
{
    int l,r,i;
    query(){}
    query(int _l,int _r,int _i)
    {
        l=_l;
        r=_r;
        i=_i;
    }
};

struct edge
{
    int x,y;
    edge(){}
    edge(int _x,int _y)
    {
        x=_x;
        y=_y;
    }
};

int n,m,k;
query a[200001];
pair<int,int> e[200001],q[200001];

void read()
{
    cin>>n>>m>>k;
    for(int i=1;i<=m;i++)
    {
        int x,y;
        cin>>x>>y;
        e[i]={x,y};
    }

    for(int i=1;i<=k;i++)
    {
        int l,r;
        cin>>l>>r;
        q[i]={l,r};
        a[i]={l,r,i};
    }
}

int used[200001];
vector<int> v[200001];
bool pos;

void dfs(int i)
{
    for(int j=0;j<v[i].size();j++)
    {
        int nb=v[i][j];
        if(!used[nb])
        {
            used[nb]=1;
            if(used[i]==1)used[nb]=2;

            dfs(nb);
        }
        else if(used[i]==used[nb])pos=0;
    }
}

void slow()
{
    for(int i=1;i<=k;i++)
    {
        pos=1;
        for(int j=1;j<=n;j++)
        {
            used[j]=0;
            v[j].clear();
        }

        for(int j=1;j<q[i].first;j++)
        {
            v[e[j].first].push_back(e[j].second);
            v[e[j].second].push_back(e[j].first);
        }

        for(int j=q[i].second+1;j<=m;j++)
        {
            v[e[j].first].push_back(e[j].second);
            v[e[j].second].push_back(e[j].first);
        }

        for(int j=1;j<=n;j++)
        {
            if(!used[j])
            {
                used[j]=1;
                dfs(j);
            }
        }

        if(pos)cout<<"NO"<<endl;
        else cout<<"YES"<<endl;
    }
}


int minr[200001];
int sz[200001];
pair<int,int> p[200001];

void init()
{
    pos=1;
    for(int i=1;i<=n;i++)
        p[i]={i,0},sz[i]=1;
}

pair<int,int> parent(int x)
{
    if(x==p[x].first)return p[x];
    int curr=p[x].second;

    p[x]=parent(p[x].first);
    p[x].second+=curr;
    return p[x];
}

void unite(int x,int y)
{
    pair<int,int> pxx=parent(x);
    pair<int,int> pyy=parent(y);

    int px=pxx.first;
    int py=pyy.first;

    if(px!=py)
    {
        if(sz[px]>sz[py])swap(px,py);

        p[px]={py,pxx.second+1+pyy.second};
        sz[py]+=sz[px];
    }
    else
    {
        //cout<<x<<" "<<y<<" "<<pxx.second<<" "<<pyy.second<<endl;
        if(pxx.second%2==pyy.second%2)
            pos=0;
    }
}

void subt()
{
    for(int i=1;i<=min(200,m);i++)
    {
        //cout<<i<<endl;
        init();
        for(int j=1;j<i;j++)
        {
            unite(e[j].first,e[j].second);
            if(pos==0)
            {
                //cout<<"in"<<" "<<i<<" "<<j<<endl;
                minr[i]=m+1;
                break;
            }
        }
        for(int j=m;j>i;j--)
        {
            unite(e[j].first,e[j].second);
            if(pos==0)
            {
                //cout<<"in"<<" "<<i<<" "<<j<<endl;
                minr[i]=max(minr[i],j);
                break;
            }
        }
    }

    for(int i=1;i<=k;i++)
    {
        if(minr[q[i].first]>q[i].second)cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
}

int s;

bool cmp(query q1,query q2)
{
    int b1=q1.l/s;
    int b2=q2.l/s;
    if(q1.l%s!=0)b1++;
    if(q2.l%s!=0)b2++;

    if(b1==b2)return q1.r>q2.r;
    return q1.l<q2.l;
}

stack<pair<int,int> > st;
int cnt1,cnt2;

pair<int,int> parent2(int x)
{
    if(p[x].first==x)return p[x];
    pair<int,int> h=parent2(p[x].first);
    h.second+=p[x].second;
    return h;
}

void unite2(int x,int y,int&cnt)
{
    //cout<<x<<" + "<<y<<endl;
    pair<int,int> pxx=parent2(x);
    pair<int,int> pyy=parent2(y);

    int px=pxx.first;
    int py=pyy.first;
    if(px!=py)
    {
        if(sz[px]>sz[py])swap(px,py);

        p[px]={py,pxx.second+pyy.second+1};
        sz[py]+=sz[px];
        st.push({px,py});
        cnt++;
        //cout<<"in"<<endl;
    }
    else
    {
        if(pxx.second%2==pyy.second%2)
        {
            pos=1;
            //cout<<"fing"<<endl;
        }
    }
}

int nun;

void rollback()
{
    pair<int,int> h=st.top();
    st.pop();

    //cout<<h.first<<" - "<<h.second<<endl;
    sz[h.second]-=sz[h.first];
    p[h.first]={h.first,0};
}

int ans[200001];
bool mark;

void small()
{
    init();
    s=sqrt(m);
    sort(a+1,a+k+1,cmp);

    int bg=1;
    int curr=m;
    int pr=0;
    int all=0;
    pos=0;
    for(int i=1;i<=k;i++)
    {
        //cout<<i<<"!"<<" "<<all<<endl;
        if(all==1)
        {
            ans[a[i].i]=1;
            continue;
        }
        int b=a[i].l/s;
        if(a[i].l%s!=0)b++;
        //cout<<"i "<<a[i].l<<" "<<b<<endl;
        if(pr!=b)
        {
            if(mark)pos=0,mark=0;
            while(cnt2)
            {
                cnt2--;
                rollback();
            }
            curr=m;

            bool pc=pos;

            for(int j=bg+1;j<=(b-1)*s;j++)
            {
                //cout<<"added "<<j<<endl;
                unite2(e[j].first,e[j].second,nun);
            }

            if(pos)all=1;
            bg=(b-1)*s;
            pr=b;
        }

        bool pc1=pos;
        while(curr>a[i].r)
        {
            unite2(e[curr].first,e[curr].second,cnt2);
            curr--;
        }
        //cout<<pos<<endl;
        if(pos==1&&pc1==0)mark=1;

        bool pc=pos;
        for(int j=(b-1)*(s)+1;j<a[i].l;j++)
            unite2(e[j].first,e[j].second,cnt1);

        if(pos)ans[a[i].i]=1;

        while(cnt1)
        {
            cnt1--;
            rollback();
        }

        pos=pc;
    }

    for(int i=1;i<=k;i++)
        if(ans[i])cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
}




int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	read();
	if(k<=2000)small();
	else if(n<=2000)slow();
	else subt();

	//slow();
	return 0;
}
/*
6 8 2
1 3
1 5
1 6
2 5
2 6
3 4
3 5
5 6

1 8
8 8
*/

Compilation message (stderr)

Joker.cpp: In function 'void dfs(int)':
Joker.cpp:56:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |     for(int j=0;j<v[i].size();j++)
      |                 ~^~~~~~~~~~~~
Joker.cpp: In function 'void small()':
Joker.cpp:286:18: warning: unused variable 'pc' [-Wunused-variable]
  286 |             bool pc=pos;
      |                  ^~

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