Submission #263866

#	Time	Username	Problem	Language	Result	Execution time	Memory
263866		cheeheng	Colors (RMI18_colors)	C++14	100 / 100	960 ms	69300 KiB

colors

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;

vector<int> aList[150005];
vector<int> bList[150005];
int a[150005];
int b[150005];

ii EdgeList[200005];

pair<ii, ii> EdgeList2[200005];

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);
        }
    }
}

int p[150005];
int rank1[150005];
stack<iii> pChanges;
stack<iii> rank1Changes;

void init1(int N){
    pChanges = stack<iii>();
    rank1Changes = stack<iii>();
    for(int i = 1; i <= N; i ++){
        p[i] = i;
        rank1[i] = 0;
    }
}

int findSet(int i){
    return (p[i] == i) ? i : findSet(p[i]);
}

//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] > rank1[y]){
            pChanges.push(iii(y, p[y], t));
            p[y] = x;
        }else{
            pChanges.push(iii(x, p[x], t));
            p[x] = y;
            if(rank1[x] == rank1[y]){
                rank1Changes.push(iii(y, rank1[y], t));
                rank1[y] ++;
            }
        }
    }
}

void rollback(int t){
    while(!pChanges.empty()){
        int x, val, t1;
        tie(x, val, t1) = pChanges.top();
        if(t1 < t){break;}
        p[x] = val;
        pChanges.pop();
    }

    while(!rank1Changes.empty()){
        int x, val, t1;
        tie(x, val, t1) = rank1Changes.top();
        if(t1 < t){break;}
        rank1[x] = val;
        rank1Changes.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;
        set<int> possible;
        for(int v: aList[c]){
            possible.insert(findSet(v));
        }

        for(int u: bList[c]){
            //printf("c=%d u=%d\n", c, u);
            bool found = false;
            int x = findSet(u);

            if(possible.find(x) == possible.end()){
                satisfied[c] = false;
                break;
            }
        }
        //printf("satisfied[%d]=%d\n", c, (int)satisfied[c]);
    }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);
    }

    rollback(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 (stderr)

colors.cpp: In function 'void dfs(int, int, int, int)':
colors.cpp:131:18: warning: unused variable 'found' [-Wunused-variable]
  131 |             bool found = false;
      |                  ^~~~~
colors.cpp: In function 'int main()':
colors.cpp:154:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  154 |     scanf("%d", &t);
      |     ~~~~~^~~~~~~~~~
colors.cpp:156:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  156 |         scanf("%d%d", &N, &M);
      |         ~~~~~^~~~~~~~~~~~~~~~
colors.cpp:164:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  164 |             scanf("%d", &a[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", &b[i]);
      |             ~~~~~^~~~~~~~~~~~~
colors.cpp:175:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  175 |             scanf("%d%d", &u, &v);
      |             ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 15 / 15
• Subtask 2: 7 / 7
• Subtask 3: 8 / 8
• Subtask 4: 15 / 15
• Subtask 5: 7 / 7
• Subtask 6: 16 / 16
• Subtask 7: 10 / 10
• Subtask 8: 22 / 22