| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 263791 |
2020-08-14T02:09:49 Z |
cheeheng |
Colors (RMI18_colors) |
C++14 |
|
564 ms |
224832 KB |
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> ii;
vector<int> aList[150005];
vector<int> bList[150005];
int a[150005];
int b[150005];
ii EdgeList[150005];
pair<ii, ii> EdgeList2[150005];
int N, M, P;
vector<ii> edges[5+(1<<19)];
void init(int i = 1, int s = 1, int e = N){
int l = (i<<1);
int r = (i<<1)|1;
int m = (s+e)>>1;
edges[i] = vector<ii>();
if(s == e){
}else{
init(l, s, m);
init(r, m+1, e);
}
}
void addEdge(int u, int v, int x, int y, int i = 1, int s = 1, int e = N){
if(x <= s && e <= y){
//printf("addEdge(%d, %d, %d, %d, %d, %d, %d)\n", u, v, x, y, i, s, e);
edges[i].push_back(ii(u, v));
return;
}else{
int l = (i<<1);
int r = (i<<1)|1;
int m = (s+e)>>1;
if(y <= m){
addEdge(u, v, x, y, l, s, m);
}else if(x > m){
addEdge(u, v, x, y, r, m+1, e);
}else{
addEdge(u, v, x, y, l, s, m);
addEdge(u, v, x, y, r, m+1, e);
}
}
}
stack<ii> p[150005];
stack<ii> rank1[150005];
void init1(int N){
for(int i = 1; i <= N; i ++){
while(!p[i].empty()){
p[i].pop();
}
while(!rank1[i].empty()){
rank1[i].pop();
}
p[i].push(ii(i, 0));
rank1[i].push(ii(0, 0));
}
}
int findSet(int i){
return (p[i].top().first == i) ? i : findSet(p[i].top().first);
}
//set<int> changed;
void unionSet(int u, int v, int t){
int x = findSet(u);
int y = findSet(v);
if(x != y){
if(rank1[x].top().first > rank1[y].top().first){
p[y].push(ii(x, t));
}else{
p[x].push(ii(y, t));
if(rank1[x].top().first == rank1[y].top().first){
int temp = rank1[y].top().first;
rank1[y].push(ii(temp+1, t));
}
}
}
}
void rollback(int u, int t){
while(!p[u].empty() && p[u].top().second >= t){
p[u].pop();
}
while(!rank1[u].empty() && rank1[u].top().second >= t){
rank1[u].pop();
}
}
bool satisfied[150005];
void dfs(int t = 1, int i = 1, int s = 1, int e = N){
//printf("dfs(%d, %d, %d, %d)\n", t, i, s, e);
for(ii edge: edges[i]){
int u, v;
tie(u, v) = edge;
unionSet(u, v, t);
//assert(b[u] <= s && e <= a[u] && b[v] <= s && e <= a[v]);
//printf("Edge: %d %d %d\n", u, v, t);
}
if(s == e){
int c = s;
satisfied[c] = true;
for(int u: bList[c]){
//printf("c=%d u=%d\n", c, u);
bool boleh = false;
for(int v: aList[c]){
//printf("%d %d\n", u, v);
int x = findSet(u);
int y = findSet(v);
if(x == y){
boleh = true;
break;
}
}
if(!boleh){
satisfied[c] = false;
break;
}
}
//printf("satisfied[%d]=%d\n", c, (int)satisfied[c]);
return;
}else{
int l = (i<<1);
int r = (i<<1)|1;
int m = (s+e)>>1;
dfs(t+1, l, s, m);
dfs(t+1, r, m+1, e);
}
for(int i = 1; i <= N; i ++){
rollback(i, t);
}
}
int main(){
int t;
scanf("%d", &t);
while(t --){
scanf("%d%d", &N, &M);
for(int i = 1; i <= N; i ++){
aList[i].clear();
bList[i].clear();
}
for(int i = 1; i <= N; i ++){
scanf("%d", &a[i]);
aList[a[i]].push_back(i);
}
for(int i = 1; i <= N; i ++){
scanf("%d", &b[i]);
bList[b[i]].push_back(i);
}
for(int i = 0; i < M; i ++){
int u, v;
scanf("%d%d", &u, &v);
EdgeList[i] = ii(u, v);
}
int ans = 1;
for(int i = 1; i <= N; i ++){
if(a[i] < b[i]){
ans = 0;
break;
}
}
if(ans == 0){
printf("%d\n", ans);
continue;
}
P = 0;
for(int i = 0; i < M; i ++){
int u, v;
tie(u, v) = EdgeList[i];
int s = max(b[u], b[v]);
int e = min(a[u], a[v]);
if(s <= e){
EdgeList2[P ++] = make_pair(ii(u, v), ii(s, e));
}
}
init();
for(int i = 0; i < P; i ++){
addEdge(EdgeList2[i].first.first, EdgeList2[i].first.second,
EdgeList2[i].second.first, EdgeList2[i].second.second);
}
init1(N);
for(int i = 1; i <= N; i ++){
satisfied[i] = true;
}
dfs();
ans = 1;
for(int i = 1; i <= N; i ++){
if(!satisfied[i]){
ans = 0;
break;
}
}
printf("%d\n", ans);
}
return 0;
}
Compilation message
colors.cpp: In function 'int main()':
colors.cpp:148:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
148 | scanf("%d", &t);
| ~~~~~^~~~~~~~~~
colors.cpp:150:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
150 | scanf("%d%d", &N, &M);
| ~~~~~^~~~~~~~~~~~~~~~
colors.cpp:158:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
158 | scanf("%d", &a[i]);
| ~~~~~^~~~~~~~~~~~~
colors.cpp:163:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
163 | scanf("%d", &b[i]);
| ~~~~~^~~~~~~~~~~~~
colors.cpp:169:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
169 | scanf("%d%d", &u, &v);
| ~~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
311 ms |
223224 KB |
Output is correct |
| 2 |
Correct |
256 ms |
222200 KB |
Output is correct |
| 3 |
Correct |
203 ms |
222124 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
299 ms |
223608 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
312 ms |
223224 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
312 ms |
223224 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
311 ms |
223224 KB |
Output is correct |
| 2 |
Correct |
256 ms |
222200 KB |
Output is correct |
| 3 |
Correct |
203 ms |
222124 KB |
Output is correct |
| 4 |
Incorrect |
312 ms |
223224 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
564 ms |
224832 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
269 ms |
222584 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
311 ms |
223224 KB |
Output is correct |
| 2 |
Correct |
256 ms |
222200 KB |
Output is correct |
| 3 |
Correct |
203 ms |
222124 KB |
Output is correct |
| 4 |
Correct |
299 ms |
223608 KB |
Output is correct |
| 5 |
Incorrect |
312 ms |
223224 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
