oj.uz

Submission #290734

# Submission time Handle Problem Language Result Execution time Memory
290734 2020-09-04T11:45:29 Z crossing0ver Colors (RMI18_colors) C++17
7 / 100
 227 ms 7148 KB 
#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

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

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 104 ms 5368 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 5532 KB Output is correct

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 88 ms 5368 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 88 ms 5368 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 104 ms 5368 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 227 ms 7148 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 37 ms 4608 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 104 ms 5368 KB Output isn't correct
2 Halted 0 ms 0 KB -