# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1106302 | lovrot | Colors (RMI18_colors) | C++17 | 106 ms | 33352 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <cstdio>
#include <vector>
#include <set>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int N = 3e5 + 10;
int n, m, a[N], b[N];
vector<int> g[N], col[N];
int un[N];
set<int> in[N];
int trazi(int u) {
return un[u] == u ? u : un[u] = trazi(un[u]);
}
void unija(int u, int v) {
u = trazi(u);
v = trazi(v);
if(u == v) { return; }
if(in[u].size() < in[v].size()) { swap(u, v); }
for(int x : in[v]) { in[u].insert(x); }
un[v] = u;
}
void solve() {
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; ++i) {
scanf("%d", a + i);
col[i].clear();
}
for(int i = 1; i <= n; ++i) {
scanf("%d", b + i);
un[i] = i;
g[i].clear();
in[i].clear();
in[i].insert(a[i]);
col[b[i]].push_back(i);
}
for(; m--; ) {
int u, v; scanf("%d%d", &u, &v);
g[u].push_back(v);
g[v].push_back(u);
}
for(int i = 1; i <= n; ++i) {
for(int u : col[i]) {
for(int v : g[u]) {
if(b[v] <= b[u]) {
unija(u, v);
}
}
}
for(int u : col[i]) {
if(in[trazi(u)].find(b[u]) == in[trazi(u)].end()) {
printf("0\n");
return;
}
}
}
printf("1\n");
return;
}
int main() {
int t;
scanf("%d", &t);
for(; t--; ) solve();
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |