oj.uz

Submission #1095136

# Submission time Handle Problem Language Result Execution time Memory
1095136 2024-10-01T11:20:57 Z simona1230 Joker (BOI20_joker) C++17
25 / 100
 1309 ms 17616 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*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();
	return 0;
}

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

Subtask #1
0 / 6.0

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

Subtask #2
0 / 8.0

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

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4952 KB Output is correct
2 Correct 2 ms 4952 KB Output is correct
3 Correct 697 ms 16464 KB Output is correct
4 Correct 1309 ms 16976 KB Output is correct
5 Correct 325 ms 17488 KB Output is correct
6 Correct 328 ms 16464 KB Output is correct
7 Correct 302 ms 16356 KB Output is correct
8 Correct 472 ms 15184 KB Output is correct
9 Correct 467 ms 15792 KB Output is correct
10 Correct 717 ms 17236 KB Output is correct
11 Correct 721 ms 16264 KB Output is correct
12 Correct 712 ms 17488 KB Output is correct
13 Correct 581 ms 15452 KB Output is correct
14 Correct 449 ms 15964 KB Output is correct
15 Correct 641 ms 16776 KB Output is correct
16 Correct 726 ms 17616 KB Output is correct

Subtask #4
0 / 10.0

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

Subtask #5
0 / 22.0

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

Subtask #6
0 / 29.0

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