# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
261821 | cheeheng | Colors (RMI18_colors) | C++14 | 92 ms | 7552 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 <bits/stdc++.h>
using namespace std;
typedef pair<int, int> ii;
vector<int> AdjList[150005];
int a[150005];
int b[150005];
ii ab[150005];
int deg[150005];
bool visited[150005];
int c[150005];
int d[150005];
int pos[150005];
vector<int> toposort;
void dfs1(int u){
if(visited[u]){return;}
visited[u] = true;
for(int v: AdjList[u]){
if(!visited[v]){
dfs1(v);
}
}
toposort.push_back(u);
}
int main(){
int t;
scanf("%d", &t);
while(t --){
int N, M;
scanf("%d%d", &N, &M);
for(int i = 1; i <= N; i ++){
AdjList[i].clear();
deg[i] = 0;
}
set<int> s1;
for(int i = 1; i <= N; i ++){
scanf("%d", &a[i]);
s1.insert(a[i]);
}
for(int i = 1; i <= N; i ++){
scanf("%d", &b[i]);
}
for(int i = 0; i < M; i ++){
int u, v;
scanf("%d%d", &u, &v);
AdjList[u].push_back(v);
AdjList[v].push_back(u);
deg[u] ++;
deg[v] ++;
}
int ans = 1;
for(int i = 1; i <= N; i ++){
if(b[i] > a[i] || s1.find(b[i]) == s1.end()){
ans = 0;
break;
}
}
if(ans == 0){
printf("0\n");
continue;
}
int starVertex = -1;
for(int i = 1; i <= N; i ++){
if(deg[i] == N-1){
starVertex = i;
break;
}
}
int cntDeg1 = 0;
for(int i = 1; i <= N; i ++){
cntDeg1 += (deg[i] == 1);
}
if((long long)M == (long long)N*(N-1)/2){
multiset<int> s;
for(int i = 1; i <= N; i ++){
ab[i] = ii(a[i], b[i]);
s.insert(a[i]);
}
sort(ab+1, ab+(N+1), greater<ii>());
for(int i = 1; i <= N; i ++){
if(ab[i].first == ab[i].second){continue;}
if(ab[i].first < ab[i].second){
ans = 0;
break;
}
if(s.find(ab[i].second) != s.end()){
}else{
ans = 0;
break;
}
s.erase(s.find(ab[i].first));
}
printf("%d\n", ans);
continue;
}
if(starVertex != -1 && M == N-1){
for(int i = 1; i <= N; i ++){
if(i == starVertex){continue;}
if(b[i] <= a[starVertex] && b[i] >= b[starVertex] || b[i] == a[i]){
}else{
ans = 0;
break;
}
}
printf("%d\n", ans);
continue;
}
if(cntDeg1 == 2 && M == N-1){
int root = -1;
for(int i = 1; i <= N; i ++){
if(deg[i] == 1){
root = i;
break;
}
}
for(int i = 1; i <= N; i ++){
visited[i] = 0;
}
toposort = vector<int>();
dfs1(root);
/*
for(int i = 1; i <= N; i ++){
printf("%d ", toposort[i-1]);
}
printf("\n");
*/
for(int i = 1; i <= N; i ++){
pos[toposort[i-1]] = i;
}
for(int i = 1; i <= N; i ++){
c[pos[i]] = a[i];
d[pos[i]] = b[i];
}
/*
printf("DEBUG:\n");
for(int i = 1; i <= N; i ++){
printf("%d ", c[i]);
}
printf("\n");
for(int i = 1; i <= N; i ++){
printf("%d ", d[i]);
}
printf("\n");
*/
c[N+1] = -1;
d[N+1] = -1;
int curVal = d[1];
int rangeMin = c[1];
ans = 1;
for(int i = 2; i <= N+1; i ++){
if(d[i] != d[i-1]){
if(rangeMin != curVal){
ans = 0;
break;
}
rangeMin = c[i];
curVal = d[i];
}else{
rangeMin = min(c[i], rangeMin);
}
}
printf("%d\n", ans);
continue;
}
throw;
}
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... |