oj.uz

Submission #261699

# Submission time Handle Problem Language Result Execution time Memory
261699 2020-08-12T02:13:26 Z oolimry Colors (RMI18_colors) C++14
100 / 100
 1026 ms 112996 KB 
#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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 33244 KB Output is correct
2 Correct 44 ms 19064 KB Output is correct
3 Correct 12 ms 11904 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 19704 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 33784 KB Output is correct
2 Correct 57 ms 19192 KB Output is correct
3 Correct 13 ms 12032 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 33784 KB Output is correct
2 Correct 57 ms 19192 KB Output is correct
3 Correct 13 ms 12032 KB Output is correct
4 Correct 243 ms 58660 KB Output is correct
5 Correct 671 ms 83216 KB Output is correct
6 Correct 1026 ms 106324 KB Output is correct

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 33244 KB Output is correct
2 Correct 44 ms 19064 KB Output is correct
3 Correct 12 ms 11904 KB Output is correct
4 Correct 130 ms 33784 KB Output is correct
5 Correct 57 ms 19192 KB Output is correct
6 Correct 13 ms 12032 KB Output is correct
7 Correct 118 ms 33532 KB Output is correct
8 Correct 48 ms 19064 KB Output is correct
9 Correct 16 ms 12032 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 235 ms 57720 KB Output is correct
2 Correct 619 ms 83584 KB Output is correct
3 Correct 645 ms 82664 KB Output is correct

Subtask #7
10.0 / 10.0

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

Subtask #8
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 33244 KB Output is correct
2 Correct 44 ms 19064 KB Output is correct
3 Correct 12 ms 11904 KB Output is correct
4 Correct 93 ms 19704 KB Output is correct
5 Correct 130 ms 33784 KB Output is correct
6 Correct 57 ms 19192 KB Output is correct
7 Correct 13 ms 12032 KB Output is correct
8 Correct 243 ms 58660 KB Output is correct
9 Correct 671 ms 83216 KB Output is correct
10 Correct 1026 ms 106324 KB Output is correct
11 Correct 118 ms 33532 KB Output is correct
12 Correct 48 ms 19064 KB Output is correct
13 Correct 16 ms 12032 KB Output is correct
14 Correct 235 ms 57720 KB Output is correct
15 Correct 619 ms 83584 KB Output is correct
16 Correct 645 ms 82664 KB Output is correct
17 Correct 53 ms 16248 KB Output is correct
18 Correct 27 ms 12920 KB Output is correct
19 Correct 19 ms 12160 KB Output is correct
20 Correct 133 ms 25848 KB Output is correct
21 Correct 630 ms 80876 KB Output is correct
22 Correct 997 ms 112996 KB Output is correct