제출 #263791

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
263791		cheeheng	Colors (RMI18_colors)	C++14	22 / 100	564 ms	224832 KiB

colors

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

컴파일 시 표준 에러 (stderr) 메시지

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);
      |             ~~~~~^~~~~~~~~~~~~~~~

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