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 <algorithm>
#include <vector>
#include <array>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <chrono>
#include <random>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cstring>
#include <iomanip>
#include <bitset>
#include <limits.h>
#include <cassert>
#define fr first
#define sc second
using namespace std;
#define int long long
const int N = (2e5)+5;
int p[N], sz[N], col[N];
stack<int> adj[N];
int find(int a)
{
if(p[a] == a)
{
return a;
}
return find(p[a]);
}
int add_edge(int a, int b)
{
int ca = find(a);
int cb = find(b);
if(ca == cb)
{
if(col[a] == col[b])
{
return -1;
}
return 1;
}
if(sz[ca] < sz[cb])
{
swap(a, b);
swap(ca, cb);
}
sz[ca] += sz[cb];
p[cb] = ca;
if(col[a] != col[b])
{
while(!adj[cb].empty())
{
adj[ca].push(adj[cb].top());
adj[cb].pop();
}
return 1;
}
while(!adj[cb].empty())
{
adj[ca].push(adj[cb].top());
col[adj[cb].top()] = 1-col[adj[cb].top()];
adj[cb].pop();
}
return 1;
}
void solve()
{
int n, m, q;
cin >> n >> m >> q;
vector<pair<int, int> > e(m+1);
for(int i = 1; i <= m; i++)
{
cin >> e[i].fr >> e[i].sc;
}
vector<int> bruh(m+1);
for(int i = 1; i <= m; i++)
{
for(int j = 1; j <= n; j++)
{
p[j] = j;
sz[j] = 1;
col[j] = 0;
while(!adj[j].empty())
{
adj[j].pop();
}
adj[j].push(j);
}
int ans = 1;
// cout << "I : " << i << endl;
for(int j = 1; j <= i-1; j++)
{
ans = min(ans, add_edge(e[j].fr, e[j].sc));
//cout << e[j].fr << " " << e[j].sc << " " << add_edge(e[j].fr, e[j].sc) << endl;
}
// cout << "I: " << i << " " << ans << endl;
// for(int i = 1; i <= n; i++)
// {
// cout << col[i] << endl;
// }
// cout << "FIND 1 " << find(1) << endl;
// cout << "SZ 1 " << sz[1] << endl;
if(ans == -1)
{
bruh[i] = m;
continue;
}
for(int j = m; j >= i; j--)
{
ans = min(ans, add_edge(e[j].fr, e[j].sc));
if(ans == -1)
{
bruh[i] = j-1;
break;
}
}
}
// for(int i = 1; i <= m; i++)
// {
// cout << bruh[i] << " ";
// }
for(int i = 0; i < q; i++)
{
int l, r;
cin >> l >> r;
if(r <= bruh[l])
{
cout << "YES" << endl;
}
else
{
cout << "NO" << endl;
}
}
}
int32_t main()
{
ios_base::sync_with_stdio(false);cin.tie(0);
int t = 1;
while(t--)
{
solve();
}
}
/*
*/
/*
#include <iostream>
#include <algorithm>
#include <vector>
#include <array>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <chrono>
#include <random>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cstring>
#include <iomanip>
#include <bitset>
#include <cassert>
*/
# | 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... |