oj.uz

Submission #262106

# Submission time Handle Problem Language Result Execution time Memory
262106 2020-08-12T11:02:31 Z errorgorn Colors (RMI18_colors) C++14
100 / 100
 924 ms 140292 KB 
//雪花飄飄北風嘯嘯
//天地一片蒼茫

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ii,ll>
#define fi first
#define se second
#define endl '\n'
#define debug(x) cout << #x << " is " << x << endl;

#define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()

#define indexed_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>
//change less to less_equal for non distinct pbds, but erase will bug

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

struct UFDS{
	int p[150005];
	int s[150005];
	vector<ii> ops;
	
	void reset(int n){
		ops.clear();
		
		rep(x,0,n){
			p[x]=x;
			s[x]=1;
		}
	}
	
	int find(int i){
		if (p[i]==i) return i;
		else return find(p[i]);
	}
	
	void unions(int i,int j){
		//cout<<"adding: "<<i<<" "<<j<<endl;
		i=find(i),j=find(j);
		
		if (i==j) return;
		if (s[i]<s[j]) swap(i,j);
		
		p[j]=i;
		s[i]+=s[j];
		ops.push_back(ii(i,j));
	}
	
	void roll(int ss){
		while (sz(ops)!=ss){
			//cout<<"erasing: "<<ops.back().fi<<" "<<ops.back().se<<endl;
			s[ops.back().fi]-=s[ops.back().se];
			p[ops.back().se]=ops.back().se;
			ops.pop_back();
		}
	}	
} ufds;

int n,m;
int arr[150005];
int brr[150005];
vector<int> posa[150005];
vector<int> posb[150005];

bool has[150005];

int ans;

struct node{
	int s,e,m;
	vector<ii> edges;
	node *l,*r;
	
	node (int _s,int _e){
		s=_s,e=_e,m=s+e>>1;
		
		if (s!=e){
			l=new node(s,m);
			r=new node(m+1,e);
		}
	}
	
	void update(int i,int j,ii k){
		if (s==i && e==j) edges.push_back(k);
		else if (j<=m) l->update(i,j,k);
		else if (m<i) r->update(i,j,k);
		else l->update(i,m,k),r->update(m+1,j,k);
	}
	
	void dfs(){
		int curr=sz(ufds.ops);
		
		for (auto &it:edges) ufds.unions(it.fi,it.se);
		
		if (s==e){
			for (auto &it:posa[s]) has[ufds.find(it)]=true;
			for (auto &it:posb[s]) if (!has[ufds.find(it)]) ans=0;
			for (auto &it:posa[s]) has[ufds.find(it)]=false;
		}
		else{
			l->dfs();
			r->dfs();
		}
		
		ufds.roll(curr);
	}
} *root;

void solve(){
	cin>>n>>m;
	rep(x,1,n+5){
		posa[x].clear();
		posb[x].clear();
	}
	ufds.reset(n+3);
	root=new node(0,n+3);
	
	rep(x,1,n+1){
		cin>>arr[x];
		posa[arr[x]].push_back(x);
	}
	rep(x,1,n+1){
		cin>>brr[x];
		posb[brr[x]].push_back(x);
	}
	
	int a,b;
	rep(x,0,m){
		cin>>a>>b;
		int l=max(brr[a],brr[b]),r=min(arr[a],arr[b]);
		if (l<=r) root->update(l,r,ii(a,b));
	}
	
	ans=1;
	root->dfs();
	
	cout<<ans<<endl;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	int TC;
	cin>>TC;
	while (TC--){
		solve();
	}
}

Compilation message

colors.cpp: In constructor 'node::node(int, int)':
colors.cpp:85:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   s=_s,e=_e,m=s+e>>1;
               ~^~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 38836 KB Output is correct
2 Correct 45 ms 19620 KB Output is correct
3 Correct 9 ms 8832 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 27640 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 37112 KB Output is correct
2 Correct 45 ms 18168 KB Output is correct
3 Correct 10 ms 8832 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 37112 KB Output is correct
2 Correct 45 ms 18168 KB Output is correct
3 Correct 10 ms 8832 KB Output is correct
4 Correct 243 ms 70776 KB Output is correct
5 Correct 567 ms 109212 KB Output is correct
6 Correct 924 ms 140292 KB Output is correct

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 38836 KB Output is correct
2 Correct 45 ms 19620 KB Output is correct
3 Correct 9 ms 8832 KB Output is correct
4 Correct 118 ms 37112 KB Output is correct
5 Correct 45 ms 18168 KB Output is correct
6 Correct 10 ms 8832 KB Output is correct
7 Correct 122 ms 39928 KB Output is correct
8 Correct 47 ms 19192 KB Output is correct
9 Correct 13 ms 9216 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 242 ms 72312 KB Output is correct
2 Correct 594 ms 121860 KB Output is correct
3 Correct 536 ms 89304 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 18040 KB Output is correct
2 Correct 27 ms 12160 KB Output is correct
3 Correct 19 ms 10112 KB Output is correct

Subtask #8
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 38836 KB Output is correct
2 Correct 45 ms 19620 KB Output is correct
3 Correct 9 ms 8832 KB Output is correct
4 Correct 105 ms 27640 KB Output is correct
5 Correct 118 ms 37112 KB Output is correct
6 Correct 45 ms 18168 KB Output is correct
7 Correct 10 ms 8832 KB Output is correct
8 Correct 243 ms 70776 KB Output is correct
9 Correct 567 ms 109212 KB Output is correct
10 Correct 924 ms 140292 KB Output is correct
11 Correct 122 ms 39928 KB Output is correct
12 Correct 47 ms 19192 KB Output is correct
13 Correct 13 ms 9216 KB Output is correct
14 Correct 242 ms 72312 KB Output is correct
15 Correct 594 ms 121860 KB Output is correct
16 Correct 536 ms 89304 KB Output is correct
17 Correct 53 ms 18040 KB Output is correct
18 Correct 27 ms 12160 KB Output is correct
19 Correct 19 ms 10112 KB Output is correct
20 Correct 161 ms 42436 KB Output is correct
21 Correct 650 ms 122988 KB Output is correct
22 Correct 828 ms 138096 KB Output is correct