oj.uz

Submission #557939

# Submission time Handle Problem Language Result Execution time Memory
557939 2022-05-06T10:20:46 Z FatihSolak Colors (RMI18_colors) C++17
52 / 100
 3000 ms 524288 KB 
#include <bits/stdc++.h>
#define N 200005
using namespace std;
int a[N];
int b[N];
vector<int> adj[N];
set<int> s[N];
bool ok[N];
void dfs(int v,int par){
	s[v] = {a[v]};
	for(auto u:adj[v]){
		if(u == par)continue;
		dfs(u,v);
		if(s[v].size() < s[u].size())
			swap(s[v],s[u]);
		for(auto c:s[u])
			s[v].insert(c);
	}
	while(*s[v].begin() < b[v])
		s[v].erase(*s[v].begin());
	while(*s[v].rbegin() > a[v])
		s[v].erase(*s[v].rbegin());
	if(s[v].count(b[v]))
		ok[v] = 1;
}
void solve(){
	int n,m;
	cin >> n >> m;
	for(int i = 1;i<=n;i++){
		cin >> a[i];
		adj[i].clear();
		ok[i] = 0;
	}
	for(int i = 1;i<=n;i++){
		cin >> b[i];
	}
	for(int i = 1;i<=m;i++){
		int u,v;
		cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	for(int i = 1;i<=n;i++){
		if(a[i] < b[i]){
			cout << 0 << endl;
			return;
		}
	}
	if(m == 1ll*n*(n-1)/2){
		map<int,int> ok;
		for(int i = 1;i<=n;i++){
			ok[a[i]] = 1;
		}
		for(int i = 1;i<=n;i++){
			if(!ok[b[i]]){
				cout << 0 << endl;
				return;
			}
		}
		cout << 1 << endl;
		return;

	}
	bool ck = 1;
	for(int i = 1;i<=n;i++){
		if(adj[i].size() > 2)ck = 0;
	}
	if(n < 10)ck = 0;
	for(int i = 1;i<=n;i++){
		if(!ck || (adj[i].size() == 1))
			dfs(i,0);
	}
	for(int i = 1;i<=n;i++){
		if(!ok[i]){
			cout << 0 << endl;
			return;
		}
	}
	cout << 1 << endl;
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	#ifdef Local
		freopen("in.txt","r",stdin);
		freopen("out.txt","w",stdout);
	#endif
	int t = 1;
	cin >> t;
	while(t--){
		solve();
	}
	#ifdef Local
		cout << endl << fixed << setprecision(2) << 1000.0*clock()/CLOCKS_PER_SEC << " milliseconds.";
	#endif
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 642 ms 14544 KB Output is correct
2 Correct 688 ms 14724 KB Output is correct
3 Correct 785 ms 14680 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 14456 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 14432 KB Output is correct
2 Correct 32 ms 14452 KB Output is correct
3 Correct 11 ms 14548 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 14432 KB Output is correct
2 Correct 32 ms 14452 KB Output is correct
3 Correct 11 ms 14548 KB Output is correct
4 Correct 167 ms 14428 KB Output is correct
5 Correct 350 ms 25388 KB Output is correct
6 Correct 594 ms 46220 KB Output is correct

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 642 ms 14544 KB Output is correct
2 Correct 688 ms 14724 KB Output is correct
3 Correct 785 ms 14680 KB Output is correct
4 Correct 86 ms 14432 KB Output is correct
5 Correct 32 ms 14452 KB Output is correct
6 Correct 11 ms 14548 KB Output is correct
7 Correct 737 ms 14552 KB Output is correct
8 Correct 746 ms 14600 KB Output is correct
9 Correct 1118 ms 14800 KB Output is correct

Subtask #6
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2348 ms 14588 KB Output is correct
2 Execution timed out 3084 ms 18548 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 325 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #8
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 642 ms 14544 KB Output is correct
2 Correct 688 ms 14724 KB Output is correct
3 Correct 785 ms 14680 KB Output is correct
4 Correct 47 ms 14456 KB Output is correct
5 Correct 86 ms 14432 KB Output is correct
6 Correct 32 ms 14452 KB Output is correct
7 Correct 11 ms 14548 KB Output is correct
8 Correct 167 ms 14428 KB Output is correct
9 Correct 350 ms 25388 KB Output is correct
10 Correct 594 ms 46220 KB Output is correct
11 Correct 737 ms 14552 KB Output is correct
12 Correct 746 ms 14600 KB Output is correct
13 Correct 1118 ms 14800 KB Output is correct
14 Correct 2348 ms 14588 KB Output is correct
15 Execution timed out 3084 ms 18548 KB Time limit exceeded
16 Halted 0 ms 0 KB -