| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 261771 |
2020-08-12T04:43:08 Z |
tqbfjotld |
Colors (RMI18_colors) |
C++14 |
|
3000 ms |
44300 KB |
#include <bits/stdc++.h>
using namespace std;
int init[150005];
int fin[150005];
vector<int> adjl[150005];
vector<pair<int,int> > order;
queue<pair<int,int> > q;
bool visited[150005];
int counter = 0;
int n,m;
void dfs2(int node){
counter++;
assert(counter<=n);
for (auto x : adjl[node]){
if (init[x]<=init[node] || fin[x]>init[node]){
continue;
}
init[x] = init[node];
dfs2(x);
}
}
int counter2 = 0;
struct node{
int s,e,v;
int lazy;
bool flag;
node *l,*r;
node (int _s, int _e){
s = _s;
e = _e;
v = 0;
flag = false;
if (s!=e){
l = new node(s,(s+e)/2);
r = new node((s+e)/2+1,e);
}
}
void proc(){
if (!flag) return;
v = lazy;
if (s!=e){
l->flag = true;
r->flag = true;
l->lazy = lazy;
r->lazy = lazy;
}
flag = false;
}
void upd(int a,int b, int val){
//printf("upd %d %d %d to %d %d\n",a,b,val,s,e);
proc();
if (a<=s && e<=b) {
lazy = val;
flag = true;
return;
}
if (b<=(s+e)/2){
l->upd(a,b,val);
}
else if (a>(s+e)/2){
r->upd(a,b,val);
}
else {
l->upd(a,b,val);
r->upd(a,b,val);
}
l->proc();r->proc();
v = min(l->v,r->v);
}
int qu(int a, int b){
//printf("qu %d %d to %d %d\n",a,b,s,e);
proc();
if (a<=s && e<=b) {
return v;
}
else if (b<=(s+e)/2){
return l->qu(a,b);
}
else if (a>(s+e)/2){
return r->qu(a,b);
}
else return min(l->qu(a,b),r->qu(a,b));
}
}*ro1,*ro2;
int main(){
int test;
scanf("%d",&test);
while (test--){
scanf("%d%d",&n,&m);
counter2 += n*n;
//assert(counter2<=5000000);
for (int x = 1; x<=n; x++){
scanf("%d",&init[x]);
adjl[x].clear();
}
bool poss1 = true;
order.clear();
for (int x = 1; x<=n; x++){
scanf("%d",&fin[x]);
if (fin[x]>init[x]) poss1 = false;
order.push_back({init[x],x});
}
sort(order.begin(),order.end(),greater<pair<int,int> >());
for (int x = 0; x<m; x++){
int a,b;
scanf("%d%d",&a,&b);
adjl[a].push_back(b);
adjl[b].push_back(a);
}
if (!poss1) {
printf("0\n");
continue;
}
if (n==1){
printf(init[1]==fin[1]?"1\n":"0\n");
continue;
}
bool poss = true;
/*for (auto x : order){
for (int x = 1; x<=n; x++) visited[x] = false;
if (!dfs(x.second,fin[x.second],fin[x.second])){
printf("0\n");
poss = false;
break;
}
}*/
if (counter2<=5000000 && true){
for (auto x : order){
counter = 0;
dfs2(x.second);
}
for (int x = 1; x<=n; x++){
if (init[x]!=fin[x]){
poss = false;
printf("0\n");
break;
}
}
if (poss){
printf("1\n");
}
}
else{
vector<int> seq;
vector<int> pos;
int cur = 1;
int prev = -1;
for (int x = 1; x<=n; x++){
if (adjl[x].size()==1) cur = x;
pos.push_back(0);
}
pos.push_back(0);
while (seq.size()<n){
seq.push_back(cur);
for (auto x : adjl[cur]){
if (x!=prev){
prev = cur;
cur = x;
break;
}
}
}
for (int x = 0; x<n; x++){
pos[seq[x]] = x+1;
//printf("pos %d = %d\n",seq[x],x+1);
}
ro1 = new node(0,n+1);
ro2 = new node(0,n+1);
for (int x = 1; x<=n; x++){
ro1->upd(pos[x],pos[x],init[x]);
ro2->upd(pos[x],pos[x],-fin[x]);
}
for (auto x : order){
init[x.second] = ro1->qu(pos[x.second],pos[x.second]);
int r1 = pos[x.second];
int r2 = n+1;
while (r1+1<r2){
int md = (r1+r2)/2;
if (ro1->qu(pos[x.second],md)<init[x.second] || ro2->qu(pos[x.second],md)<-init[x.second]){
r2 = md;
}
else r1 = md;
}
int l1 = 0;
int l2 = pos[x.second];
while (l1+1<l2){
int md = (l1+l2)/2;
if (ro1->qu(md,pos[x.second])<init[x.second] || ro2->qu(md,pos[x.second])<-init[x.second]){
l1 = md;
}
else l2 = md;
}
ro1->upd(l2,r1,init[x.second]);
}
for (int x = 1; x<=n; x++){
init[seq[x-1]] = ro1->qu(x,x);
//printf("final cols %d = %d\n",x,init[x]);
}
for (int x = 1; x<=n; x++){
if (init[x]!=fin[x]){
poss = false;
printf("0\n");
break;
}
}
if (poss){
printf("1\n");
}
}
}
}
Compilation message
colors.cpp: In function 'int main()':
colors.cpp:157:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while (seq.size()<n){
~~~~~~~~~~^~
colors.cpp:91:6: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&test);
~~~~~^~~~~~~~~~~~
colors.cpp:93:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&n,&m);
~~~~~^~~~~~~~~~~~~~
colors.cpp:97:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&init[x]);
~~~~~^~~~~~~~~~~~~~~
colors.cpp:103:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&fin[x]);
~~~~~^~~~~~~~~~~~~~
colors.cpp:110:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&a,&b);
~~~~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
90 ms |
3960 KB |
Output is correct |
| 2 |
Correct |
41 ms |
3960 KB |
Output is correct |
| 3 |
Correct |
16 ms |
3968 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
101 ms |
3840 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
79 ms |
3840 KB |
Output is correct |
| 2 |
Correct |
43 ms |
3840 KB |
Output is correct |
| 3 |
Correct |
6 ms |
3840 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
79 ms |
3840 KB |
Output is correct |
| 2 |
Correct |
43 ms |
3840 KB |
Output is correct |
| 3 |
Correct |
6 ms |
3840 KB |
Output is correct |
| 4 |
Correct |
454 ms |
44024 KB |
Output is correct |
| 5 |
Execution timed out |
3071 ms |
24968 KB |
Time limit exceeded |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
90 ms |
3960 KB |
Output is correct |
| 2 |
Correct |
41 ms |
3960 KB |
Output is correct |
| 3 |
Correct |
16 ms |
3968 KB |
Output is correct |
| 4 |
Correct |
79 ms |
3840 KB |
Output is correct |
| 5 |
Correct |
43 ms |
3840 KB |
Output is correct |
| 6 |
Correct |
6 ms |
3840 KB |
Output is correct |
| 7 |
Correct |
89 ms |
3840 KB |
Output is correct |
| 8 |
Correct |
36 ms |
3840 KB |
Output is correct |
| 9 |
Correct |
17 ms |
3968 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
276 ms |
44300 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
46 ms |
3968 KB |
Output is correct |
| 2 |
Correct |
23 ms |
3968 KB |
Output is correct |
| 3 |
Correct |
26 ms |
3964 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
90 ms |
3960 KB |
Output is correct |
| 2 |
Correct |
41 ms |
3960 KB |
Output is correct |
| 3 |
Correct |
16 ms |
3968 KB |
Output is correct |
| 4 |
Correct |
101 ms |
3840 KB |
Output is correct |
| 5 |
Correct |
79 ms |
3840 KB |
Output is correct |
| 6 |
Correct |
43 ms |
3840 KB |
Output is correct |
| 7 |
Correct |
6 ms |
3840 KB |
Output is correct |
| 8 |
Correct |
454 ms |
44024 KB |
Output is correct |
| 9 |
Execution timed out |
3071 ms |
24968 KB |
Time limit exceeded |
| 10 |
Halted |
0 ms |
0 KB |
- |
