Submission #261699

#	Time	Username	Problem	Language	Result	Execution time	Memory
261699		oolimry	Colors (RMI18_colors)	C++14	100 / 100	1026 ms	112996 KiB

colors

#include <bits/stdc++.h>
#define all(x) ((x).begin(), (x).end())
#define sz(x) ((int) (x).size())
using namespace std;
typedef pair<int,int> ii;

bool die = false;

vector<int> adj[150005];
int start[150005];
int target[150005];
vector<int> atStart[150005];
vector<int> atTarget[150005];
bool vis[150005];

int p[150005];
int rak[150005];
vector<ii> history;

void reset(int n){
	for(int i = 0;i <= n;i++){
		p[i] = i;
		rak[i] = 1;
	}
}

int findSet(int u){
	if(u == p[u]) return u;
	else return findSet(p[u]);
}

bool unionSet(int u, int v){
	u = findSet(u), v = findSet(v);
	if(u == v) return false;
	
	if(rak[u] > rak[v]) swap(u,v);
	p[u] = v;
	if(rak[u] == rak[v]) rak[v]++;
	
	history.push_back(ii(u,v));
	return true;
}

void rollback(){
	ii t = history.back(); history.pop_back();
	p[t.first] = t.first;
}

struct node{
	int s, e, m;
	vector<ii> upd;
	node *l, *r;
	
	node(int S, int E){
		s = S, e = E, m = (S+E)/2;
		if(s != e){
			l = new node(s, m);
			r = new node(m+1, e);
		}
	}
	
	void update(int S, int E, ii X){
		if(S == s && e == E){
			upd.push_back(X);
		}
		else if(E <= m) l->update(S,E,X);
		else if(S >= m+1) r->update(S,E,X);
		else{
			l->update(S,m,X);
			r->update(m+1,E,X);
		}
	}
	
	void dfs(){
		int cnt = 0;
		for(ii E : upd){
			cnt += unionSet(E.first, E.second);
		}
		
		if(s == e){
			set<int> good;
			for(int x : atStart[s]){
				int u = findSet(x);
				good.insert(u);
			}
			
			for(int x : atTarget[s]){
				int u = findSet(x);
				if(good.find(u) == good.end()){
				//	cout << x << " " << s << "DDD\n";
					die = true;
				}
			}
		}
		
		else{
			l->dfs();
			r->dfs();
		}
		
		while(cnt--) rollback();
	}
	
} *root;

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0);
	
	int TC; cin >> TC;
	
	while(TC--){
		
		die = false;
		int n, m; cin >> n >> m;
		
		for(int i = 1;i <= n;i++){
			adj[i].clear();
			atStart[i].clear();
			atTarget[i].clear();
		}
		
		for(int i = 1;i <= n;i++) cin >> start[i];
		for(int i = 1;i <= n;i++) cin >> target[i];
		
		reset(n);
		root = new node(1,n);
		
		for(int i = 1;i <= m;i++){
			int a, b; cin >> a >> b;
			adj[a].push_back(b);
			adj[b].push_back(a);
			
			int R = min(start[a],start[b]);
			int L = max(target[a],target[b]);
			
			if(L <= R){
				root->update(L,R,ii(a,b));
			}
		}
		
		for(int i = 1;i <= n;i++){
			if(start[i] < target[i]){
				die = true;
				break;
			}
		}
		
		for(int i = 1;i <= n;i++){
			atStart[start[i]].push_back(i);
			atTarget[target[i]].push_back(i);
		}
		
		root->dfs();
		
		if(die) cout << 0;
		else cout << 1;
		cout << "\n";
	}
}

• Subtask 1: 15 / 15
• Subtask 2: 7 / 7
• Subtask 3: 8 / 8
• Subtask 4: 15 / 15
• Subtask 5: 7 / 7
• Subtask 6: 16 / 16
• Subtask 7: 10 / 10
• Subtask 8: 22 / 22