#include <bits/stdc++.h>
using namespace std;
const int M=2e5+1;
int n,m,q;
bool mark[M],vis[M],correct;
int val[M],par[M],h[M];
vector<int> com[M];
vector<pair<int,int>> ma[M],query,edges;
int mx_r_for_l[M];
bool found=0;
void dfs(int x)
{
vis[x]=1;
for(auto [y,ind]:ma[x])
{
if(mark[ind])
continue;
if(!vis[y])
{
val[y]=(val[x]+1)%2;
dfs(y);
}
else if((val[y]+1)%2!=val[x])
{
found=1;
}
}
}
bool check(int l,int r)
{
// cout<<"Check "<<l<<' '<<r<<endl;
for(int i=1;i<=n;i++)
vis[i]=0;
for(int i=0;i<m;i++)
mark[i]=(l<=i and i<=r);
found=0;
for(int i=1;i<=n;i++)
{
if(!vis[i])
{
dfs(i);
}
}
// cout<<"Answer "<<found<<endl;
return found;
}
void init(){
correct=1;
for(int i=1;i<=n;i++)
{
h[i]=0;
par[i]=i;
com[i]={i};
}
}
void add_edge(int ind)
{
int u=edges[ind].first;
int v=edges[ind].second;
int pu=par[u];
int pv=par[v];
// cout<<"Hola "<<u<<' '<<v<<endl;
// cout<<pu<<' '<<pv<<endl;
if(pu==pv)
{
if(h[u]==h[v])
{
correct=0;
}
}
else{
int cp=(h[u]!=h[v]);
u=pu;
v=pv;
if(com[u].size()>com[v].size())
swap(u,v);
for(auto ver:com[u])
{
com[v].push_back(ver);
par[ver]=v;
h[ver]=(h[ver]+cp)%2;
}
com[u].clear();
}
}
int main()
{
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(0);
cin>>n>>m>>q;
for(int i=0;i<m;i++)
{
int a,b;
cin>>a>>b;
// cout<<i+1<<"th edge is "<<a<<' '<<b<<endl;
ma[a].push_back({b,i});
ma[b].push_back({a,i});
edges.push_back({a,b});
}
vector<int> difl={-1};
for(int lp=0;lp<q;lp++)
{
int l,r;
cin>>l>>r;
l--;
r--;
query.push_back({l,r});
difl.push_back(l);
}
sort(begin(difl),end(difl));
for(int i=1;i<difl.size();i++)
{
if(difl[i-1]!=difl[i])
{
int l=difl[i];
int r=l;
init();
while(r<m and correct)
{
add_edge(r);
if(correct)
r++;
}
// cout<<"Hola r = "<<r<<" for l = "<<l<<endl;
mx_r_for_l[l]=r-1;
}
}
for(auto [l,r]:query)
{
if(mx_r_for_l[l]>=r)
{
// cout<<"Query "<<l<<' '<<r<<endl;
cout<<"YES"<<'\n';
}
else{
cout<<"NO"<<'\n';
}
}
return 0;
}
Compilation message
Joker.cpp: In function 'int main()':
Joker.cpp:113:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
113 | for(int i=1;i<difl.size();i++)
| ~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
12632 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
12632 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
12632 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
12632 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
12632 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
12632 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
