oj.uz

Submission #263866

# Submission time Handle Problem Language Result Execution time Memory
263866 2020-08-14T02:48:37 Z cheeheng Colors (RMI18_colors) C++14
100 / 100
 960 ms 69300 KB 
#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

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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 19784 KB Output is correct
2 Correct 50 ms 19712 KB Output is correct
3 Correct 16 ms 19968 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 19832 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 19712 KB Output is correct
2 Correct 55 ms 19712 KB Output is correct
3 Correct 17 ms 19968 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 19712 KB Output is correct
2 Correct 55 ms 19712 KB Output is correct
3 Correct 17 ms 19968 KB Output is correct
4 Correct 266 ms 19712 KB Output is correct
5 Correct 584 ms 33232 KB Output is correct
6 Correct 960 ms 56880 KB Output is correct

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 19784 KB Output is correct
2 Correct 50 ms 19712 KB Output is correct
3 Correct 16 ms 19968 KB Output is correct
4 Correct 128 ms 19712 KB Output is correct
5 Correct 55 ms 19712 KB Output is correct
6 Correct 17 ms 19968 KB Output is correct
7 Correct 124 ms 19712 KB Output is correct
8 Correct 54 ms 19712 KB Output is correct
9 Correct 18 ms 19968 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 243 ms 19832 KB Output is correct
2 Correct 547 ms 33148 KB Output is correct
3 Correct 550 ms 45032 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 19840 KB Output is correct
2 Correct 30 ms 20148 KB Output is correct
3 Correct 23 ms 19960 KB Output is correct

Subtask #8
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 19784 KB Output is correct
2 Correct 50 ms 19712 KB Output is correct
3 Correct 16 ms 19968 KB Output is correct
4 Correct 110 ms 19832 KB Output is correct
5 Correct 128 ms 19712 KB Output is correct
6 Correct 55 ms 19712 KB Output is correct
7 Correct 17 ms 19968 KB Output is correct
8 Correct 266 ms 19712 KB Output is correct
9 Correct 584 ms 33232 KB Output is correct
10 Correct 960 ms 56880 KB Output is correct
11 Correct 124 ms 19712 KB Output is correct
12 Correct 54 ms 19712 KB Output is correct
13 Correct 18 ms 19968 KB Output is correct
14 Correct 243 ms 19832 KB Output is correct
15 Correct 547 ms 33148 KB Output is correct
16 Correct 550 ms 45032 KB Output is correct
17 Correct 61 ms 19840 KB Output is correct
18 Correct 30 ms 20148 KB Output is correct
19 Correct 23 ms 19960 KB Output is correct
20 Correct 157 ms 19960 KB Output is correct
21 Correct 573 ms 39432 KB Output is correct
22 Correct 872 ms 69300 KB Output is correct