Submission #1093976

#	Time	Username	Problem	Language	Result	Execution time	Memory
1093976		simona1230	Joker (BOI20_joker)	C++17	41 / 100	1251 ms	17876 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^pyy.second^1}};
        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 main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	read();
	/*if(n<=2000)slow();
	else*/ subt();
	return 0;
}

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++)
      |                 ~^~~~~~~~~~~~

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