This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <iostream>
#include <vector>
using namespace std;
const int N = (1<<18) + 1;
vector<pair<int,int>> nei[N];
int seen[N],h[N];
int cur = 1,l,r;
bool odd;
void dfs(int u,int k = 1){
seen[u] = cur;
h[u] = k;
for (auto [i,j] : nei[u]){
if (j <= r and j >= l)
continue;
if (seen[i] == cur){
if ((h[u] - h[i]) % 2 == 0)
odd = true;
}
else
dfs(i,k+1);
}
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n,m,q;
cin>>n>>m>>q;
for (int i=1;i<=m;i++){
int a,b;
cin>>a>>b;
nei[a].push_back({b,i});
nei[b].push_back({a,i});
}
while (q--){
cin>>l>>r;
odd = false;
for (int i=1;i<=n;i++)
if (seen[i]!=cur)
dfs(i);
cur++;
if (odd)
cout<<"YES"<<'\n';
else
cout<<"NO"<<'\n';
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |