oj.uz

Submission #557943

# Submission time Handle Problem Language Result Execution time Memory
557943 2022-05-06T10:28:07 Z FatihSolak Colors (RMI18_colors) C++17
62 / 100
 3000 ms 46136 KB 
#include <bits/stdc++.h>
#define N 200005
#define M 3005
using namespace std;
int a[N];
int b[N];
vector<int> adj[N];
set<int> s[N];
bool ok[N];
bool can[M][M];
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;
	}
	if(m == n-1){
		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;
		return;
	}
	for(int i = 1;i<=n;i++){
		for(int j = 1;j<=n;j++){
			can[i][j] = 0;
		}
		can[i][a[i]] = 1;
	}
	for(int i = 1;i<=n;i++){
		queue<int> q;
		for(int j = 1;j<=n;j++){
			if(a[j] == i)q.push(j);
		}
		while(q.size()){
			auto tp = q.front();
			q.pop();
			for(auto u:adj[tp]){
				if(a[u] > i && b[u] <= i && !can[u][i]){
					can[u][i] = 1;
					q.push(u);
				}
			}
		}
	}
	for(int i = 1;i<=n;i++){
		if(!can[i][b[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 664 ms 14700 KB Output is correct
2 Correct 700 ms 14540 KB Output is correct
3 Correct 775 ms 14612 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 14424 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 14544 KB Output is correct
2 Correct 34 ms 14460 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 91 ms 14544 KB Output is correct
2 Correct 34 ms 14460 KB Output is correct
3 Correct 11 ms 14548 KB Output is correct
4 Correct 155 ms 14540 KB Output is correct
5 Correct 418 ms 25496 KB Output is correct
6 Correct 511 ms 46136 KB Output is correct

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 664 ms 14700 KB Output is correct
2 Correct 700 ms 14540 KB Output is correct
3 Correct 775 ms 14612 KB Output is correct
4 Correct 91 ms 14544 KB Output is correct
5 Correct 34 ms 14460 KB Output is correct
6 Correct 11 ms 14548 KB Output is correct
7 Correct 728 ms 14332 KB Output is correct
8 Correct 730 ms 14576 KB Output is correct
9 Correct 1059 ms 14808 KB Output is correct

Subtask #6
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2360 ms 14620 KB Output is correct
2 Execution timed out 3060 ms 18696 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 14676 KB Output is correct
2 Correct 30 ms 15040 KB Output is correct
3 Correct 54 ms 15976 KB Output is correct

Subtask #8
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 664 ms 14700 KB Output is correct
2 Correct 700 ms 14540 KB Output is correct
3 Correct 775 ms 14612 KB Output is correct
4 Correct 44 ms 14424 KB Output is correct
5 Correct 91 ms 14544 KB Output is correct
6 Correct 34 ms 14460 KB Output is correct
7 Correct 11 ms 14548 KB Output is correct
8 Correct 155 ms 14540 KB Output is correct
9 Correct 418 ms 25496 KB Output is correct
10 Correct 511 ms 46136 KB Output is correct
11 Correct 728 ms 14332 KB Output is correct
12 Correct 730 ms 14576 KB Output is correct
13 Correct 1059 ms 14808 KB Output is correct
14 Correct 2360 ms 14620 KB Output is correct
15 Execution timed out 3060 ms 18696 KB Time limit exceeded
16 Halted 0 ms 0 KB -