oj.uz

Submission #261698

# Submission time Handle Problem Language Result Execution time Memory
261698 2020-08-12T02:11:27 Z oolimry Colors (RMI18_colors) C++14
61 / 100
 997 ms 113104 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]);
}

void unionSet(int u, int v){
	u = findSet(u), v = findSet(v);
	if(u == v) return;
	
	if(rak[u] > rak[v]) swap(u,v);
	p[u] = v;
	if(rak[u] == rak[v]) rak[v]++;
	
	history.push_back(ii(u,v));
	//cout << u << " " << v << "A\n";
}

void rollback(){
	ii t = history.back(); history.pop_back();
	p[t.first] = t.first;
	//cout << t.first << " " << t.second << "R\n";
}

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(){
		//cout << s << " " << e << ":\n";
		for(ii E : upd){
			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();
		}
		
		for(int i = 0;i < sz(upd);i++) 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));
				//cout << a << " " << b << " " << L <<" "  << R << "\n";
			}
		}
		
		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 114 ms 34224 KB Output is correct
2 Correct 46 ms 19576 KB Output is correct
3 Correct 12 ms 12032 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 27 ms 22144 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 34680 KB Output is correct
2 Correct 50 ms 19704 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 126 ms 34680 KB Output is correct
2 Correct 50 ms 19704 KB Output is correct
3 Correct 13 ms 12032 KB Output is correct
4 Correct 258 ms 61740 KB Output is correct
5 Correct 573 ms 89672 KB Output is correct
6 Correct 997 ms 113104 KB Output is correct

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 34224 KB Output is correct
2 Correct 46 ms 19576 KB Output is correct
3 Correct 12 ms 12032 KB Output is correct
4 Correct 126 ms 34680 KB Output is correct
5 Correct 50 ms 19704 KB Output is correct
6 Correct 13 ms 12032 KB Output is correct
7 Correct 118 ms 35064 KB Output is correct
8 Correct 48 ms 19576 KB Output is correct
9 Correct 14 ms 12160 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 239 ms 58616 KB Output is correct
2 Correct 582 ms 89612 KB Output is correct
3 Correct 652 ms 89708 KB Output is correct

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 22 ms 22016 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #8
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 34224 KB Output is correct
2 Correct 46 ms 19576 KB Output is correct
3 Correct 12 ms 12032 KB Output is correct
4 Runtime error 27 ms 22144 KB Execution killed with signal 11 (could be triggered by violating memory limits)