oj.uz

Submission #261762

# Submission time Handle Problem Language Result Execution time Memory
261762 2020-08-12T04:36:41 Z tqbfjotld Colors (RMI18_colors) C++14
47 / 100
 91 ms 8480 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;
    }
    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;
        }
        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:153: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);
         ~~~~~^~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 3840 KB Output is correct
2 Correct 41 ms 3968 KB Output is correct
3 Correct 16 ms 3968 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 3872 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 3840 KB Output is correct
2 Correct 28 ms 3840 KB Output is correct
3 Correct 6 ms 3840 KB Output is correct

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 3840 KB Output is correct
2 Correct 28 ms 3840 KB Output is correct
3 Correct 6 ms 3840 KB Output is correct
4 Runtime error 60 ms 8480 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Halted 0 ms 0 KB -

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 3840 KB Output is correct
2 Correct 41 ms 3968 KB Output is correct
3 Correct 16 ms 3968 KB Output is correct
4 Correct 79 ms 3840 KB Output is correct
5 Correct 28 ms 3840 KB Output is correct
6 Correct 6 ms 3840 KB Output is correct
7 Correct 86 ms 3840 KB Output is correct
8 Correct 41 ms 3840 KB Output is correct
9 Correct 17 ms 3968 KB Output is correct

Subtask #6
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 67 ms 8184 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 3840 KB Output is correct
2 Correct 22 ms 3968 KB Output is correct
3 Correct 26 ms 3960 KB Output is correct

Subtask #8
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 3840 KB Output is correct
2 Correct 41 ms 3968 KB Output is correct
3 Correct 16 ms 3968 KB Output is correct
4 Correct 91 ms 3872 KB Output is correct
5 Correct 79 ms 3840 KB Output is correct
6 Correct 28 ms 3840 KB Output is correct
7 Correct 6 ms 3840 KB Output is correct
8 Runtime error 60 ms 8480 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Halted 0 ms 0 KB -