| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 551769 |
2022-04-21T13:59:06 Z |
oleh1421 |
Colors (BOI20_colors) |
C++17 |
|
0 ms |
208 KB |
//#pragma GCC target("avx2")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
//#define endl '\n'
using namespace __gnu_pbds;
typedef long double ld;
//#define int ll
using namespace std;
mt19937 rnd(time(NULL));
typedef long long ll;
const int N=400100;
const int K=400;
int a[N],b[N];
int ans[N];
int l[N/K+1];
int r[N/K+1];
int group[N];
int w[N];
int sz[N];
int dsu[N];
vector<pair<int,pair<int,int> > >CH;
pair<int,int>get(int x){
if (x==dsu[x]) return {x,w[x]};
auto cur=get(dsu[x]);
cur.second^=w[x];
return cur;
}
bool unite(int a,int b){
auto x=get(a);
auto y=get(b);
if (x.first==y.first){
return (x.second!=y.second);
}
if (sz[x.first]>sz[y.first]) swap(x,y);
CH.push_back({1,{x.first,dsu[x.first]}});
CH.push_back({2,{y.first,sz[y.first]}});
CH.push_back({3,{x.first,w[x.first]}});
dsu[x.first]=y.first;
sz[y.first]+=sz[x.first];
w[x.first]^=(x.second^y.second^1^w[y.first]);
return true;
}
void roll_back(){
if (!CH.empty()){
auto cur=CH.back();
CH.pop_back();
if (cur.first==1) dsu[cur.second.first]=cur.second.second;
else if (cur.first==2) sz[cur.second.first]=cur.second.second;
else w[cur.second.first]=cur.second.second;
}
}
void solve(){
int n,m,q;cin>>n>>m>>q;
for (int i=1;i<=m;i++){
cin>>a[i]>>b[i];
}
int cnt=(m+K-1)/K;
for (int i=1;i<=cnt;i++){
l[i]=max(m-i*K+1,1);
r[i]=m-(i-1)*K;
}
for (int i=1;i<=n;i++){
dsu[i]=i;
sz[i]=1;
w[i]=0;
}
l[0]=m+1;
r[0]=m;
for (int i=1;i<=cnt;i++){
bool bad=false;
for (int j=l[i];j<=m;j++){
if (!unite(a[j],b[j])) bad=true;
}
if (!bad){
for (int j=1;j<=m;j++){
if (!unite(a[j],b[j])) break;
group[j]=i;
}
}
while (!CH.empty()){
roll_back();
}
}
int last=cnt+1;
bool bad=false;
for (int i=1;i<=m;i++){
// cout<<"G "<<i<<" "<<group[i]<<endl;
while (last>group[i]){
bad=false;
last=group[i];
while (!CH.empty()){
roll_back();
}
for (int j=l[last];j<=m;j++){
if (!unite(a[j],b[j])) bad=true;
}
for (int j=1;j<i;j++){
if (!unite(a[j],b[j])) bad=true;
}
}
if (!unite(a[i],b[i])) bad=true;
// if (bad) cout<<"AAA "<<i<<endl;
int len=CH.size();
if (bad) ans[i]=m+1;
else if (last==cnt) ans[i]=0;
else {
for (int j=r[last+1];j>=l[last+1];j--){
// if (i==3) cout<<"AAAA "<<j<<endl;
if (!unite(a[j],b[j])){
ans[i]=j;
break;
}
}
}
while (CH.size()>len){
roll_back();
}
}
for (int i=1;i<=q;i++){
int l,r;cin>>l>>r;
if (ans[l-1]<=r) cout<<"NO\n";
else cout<<"YES\n";
}
}
int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int tt=1;
while (tt--){
solve();
}
return 0;
}
/**
6 8 2
1 3
1 5
1 6
2 5
2 6
3 4
3 5
5 6
4 8
4 7
**/
Compilation message
Colors.cpp: In function 'void solve()':
Colors.cpp:119:25: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
119 | while (CH.size()>len){
| ~~~~~~~~~^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
0 ms |
208 KB |
Time limit exceeded (wall clock) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
0 ms |
208 KB |
Time limit exceeded (wall clock) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
0 ms |
208 KB |
Time limit exceeded (wall clock) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
0 ms |
208 KB |
Time limit exceeded (wall clock) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
0 ms |
208 KB |
Time limit exceeded (wall clock) |
| 2 |
Halted |
0 ms |
0 KB |
- |
