oj.uz

Submission #1095153

# Submission time Handle Problem Language Result Execution time Memory
1095153 2024-10-01T12:48:30 Z simona1230 Joker (BOI20_joker) C++17
25 / 100
 1218 ms 19796 KB 
#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*(s-1)+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 5
1 3
1 5
1 6
2 5
2 6
3 4
3 5
5 6

1 3
1 2
6 8
4 7
3 5
*/

Compilation message

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
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 3 ms 6788 KB Output is correct
3 Correct 2 ms 6748 KB Output is correct
4 Correct 2 ms 6748 KB Output is correct
5 Correct 3 ms 6748 KB Output is correct
6 Incorrect 2 ms 6748 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 3 ms 6788 KB Output is correct
3 Correct 2 ms 6748 KB Output is correct
4 Correct 2 ms 6748 KB Output is correct
5 Correct 3 ms 6748 KB Output is correct
6 Incorrect 2 ms 6748 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 3 ms 6788 KB Output is correct
3 Correct 681 ms 18512 KB Output is correct
4 Correct 1218 ms 17748 KB Output is correct
5 Correct 319 ms 18512 KB Output is correct
6 Correct 301 ms 17604 KB Output is correct
7 Correct 303 ms 17668 KB Output is correct
8 Correct 432 ms 16860 KB Output is correct
9 Correct 462 ms 17836 KB Output is correct
10 Correct 709 ms 18772 KB Output is correct
11 Correct 663 ms 19588 KB Output is correct
12 Correct 685 ms 19672 KB Output is correct
13 Correct 578 ms 19540 KB Output is correct
14 Correct 437 ms 19688 KB Output is correct
15 Correct 622 ms 19660 KB Output is correct
16 Correct 698 ms 19796 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 3 ms 6788 KB Output is correct
3 Correct 2 ms 6748 KB Output is correct
4 Correct 2 ms 6748 KB Output is correct
5 Correct 3 ms 6748 KB Output is correct
6 Incorrect 2 ms 6748 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 3 ms 6788 KB Output is correct
3 Correct 2 ms 6748 KB Output is correct
4 Correct 2 ms 6748 KB Output is correct
5 Correct 3 ms 6748 KB Output is correct
6 Incorrect 2 ms 6748 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 3 ms 6788 KB Output is correct
3 Correct 2 ms 6748 KB Output is correct
4 Correct 2 ms 6748 KB Output is correct
5 Correct 3 ms 6748 KB Output is correct
6 Incorrect 2 ms 6748 KB Output isn't correct
7 Halted 0 ms 0 KB -