oj.uz

Submission #1095145

# Submission time Handle Problem Language Result Execution time Memory
1095145 2024-10-01T12:09:07 Z simona1230 Joker (BOI20_joker) C++17
25 / 100
 1261 ms 18512 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();
            }

            bool pc=pos;

            for(int j=bg;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();
        }

        if(pos!=pc)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 3
4 7
*/

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:285:18: warning: unused variable 'pc' [-Wunused-variable]
  285 |             bool pc=pos;
      |                  ^~

Subtask #1
0 / 6.0

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

Subtask #2
0 / 8.0

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

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4956 KB Output is correct
2 Correct 2 ms 4956 KB Output is correct
3 Correct 654 ms 16468 KB Output is correct
4 Correct 1261 ms 16980 KB Output is correct
5 Correct 324 ms 18512 KB Output is correct
6 Correct 305 ms 17724 KB Output is correct
7 Correct 304 ms 17744 KB Output is correct
8 Correct 432 ms 16864 KB Output is correct
9 Correct 466 ms 17204 KB Output is correct
10 Correct 713 ms 18004 KB Output is correct
11 Correct 705 ms 17492 KB Output is correct
12 Correct 729 ms 18260 KB Output is correct
13 Correct 582 ms 16912 KB Output is correct
14 Correct 456 ms 17236 KB Output is correct
15 Correct 637 ms 18000 KB Output is correct
16 Correct 708 ms 18372 KB Output is correct

Subtask #4
0 / 10.0

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

Subtask #5
0 / 22.0

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

Subtask #6
0 / 29.0

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