Submission #852042

#	Time	Username	Problem	Language	Result	Execution time	Memory
852042		allin27x	Colors (RMI18_colors)	C++17	47 / 100	3042 ms	11676 KiB

colors

#include <bits/stdc++.h>
using namespace std;

int a[(int)2e5];
int b[(int)2e5];
vector<int> adj[(int)2e5];
int vis[(int)2e5+7];

void dfs(int i, int v){
	a[i] = v; vis[i] = v;
	for (auto c: adj[i]){
		if (vis[c] == v) continue;
		if (b[c] > v) continue;
		if (a[c] < v) continue;
		dfs(c, v);
	}
}

int solve(){
	int n,m; cin>>n>>m;
	for (int i=0; i<n; i++) vis[i] = 0;
	for (int i=0; i<n; i++) adj[i].clear();
	for (int i=0; i<n; i++) cin>>a[i];
	for (int i=0; i<n; i++) cin>>b[i];
	for (int i=0; i<m; i++){
		int a,b; cin>>a>>b; a--; b--;
		adj[a].push_back(b); adj[b].push_back(a);
	}
	for (int v = n; v; v--){
		for (int i=0; i<n; i++){
			if (a[i] == v && vis[i] != v) dfs(i, v);
		}
	}
	for (int i=0; i<n; i++){
		if (a[i] != b[i]) return 0;
	}
	return 1;
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int t; cin>>t;
	while (t--){
		cout << solve() << '\n';
	}
}

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