oj.uz

Submission #262083

# Submission time Handle Problem Language Result Execution time Memory
262083 2020-08-12T10:30:46 Z errorgorn Colors (RMI18_colors) C++14
0 / 100
 279 ms 74872 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+1){
		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));
	}
	
	rep(x,1,n+1){
		if (brr[x]>arr[x]){
			cout<<0<<endl;
			return;
		}
	}
	
	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
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 118 ms 40056 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 104 ms 29048 KB Output isn't correct

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 126 ms 38456 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 126 ms 38456 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 118 ms 40056 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 279 ms 74872 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 56 ms 18684 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 118 ms 40056 KB Output isn't correct
2 Halted 0 ms 0 KB -