Submission #290734

#	Time	Username	Problem	Language	Result	Execution time	Memory
290734		crossing0ver	Colors (RMI18_colors)	C++17	7 / 100	227 ms	7148 KiB

colors

#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define pii pair<int,int>
#define vi vector<int>
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
using namespace std;
const int N = 1.5e5+5;
int n,m,a[N],b[N];
vi adj[N];
void solve() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	for (int i = 1; i <= n; i++)
		cin >> b[i];
	for (int i = 0,a,b;i < m; i++) {
		cin >> a >> b;
		adj[a].pb(b);
		adj[b].pb(a);
	}
	for (int i = 1; i <= n; i++) {
		if (a[i] < b[i]) {
			cout << "0\n";
			return;
		}
	}
	vector<pii> g(n);
	for (int i = 1; i <= n; i++)
		g[i-1] = {b[i],i};
	sort(g.rbegin(),g.rend());
	for (auto i1 : g) {
		int v = i1.se;
		int target = i1.fi;
		if (a[v] == target) continue;
		queue<int> q;
		q.push(v);
		bool flag = 0;
		vector<bool> vis(n+1);
		vis[v] = 1;
		while (!q.empty()) {
			int v = q.front();
			q.pop();
			if (a[v] == target) {
				flag = 1;
				break;
			}
			for (int i : adj[v]) 
				if (b[i] <= target && !vis[i]) {
					q.push(i);
					vis[i] = 1;
				} 
		}
		if (flag == 0) {
			cout <<"0\n";
			return;
		}
	}
	cout <<"1\n";
}
main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int t;
	cin >> t;
	while(t--) {
		solve();
		// clear
	for (int i = 1; i <= n; i++)
		adj[i].clear();
	}

}

Compilation message (stderr)

colors.cpp:63:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   63 | main() {
      |      ^

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