oj.uz

Submission #263840

# Submission time Handle Problem Language Result Execution time Memory
263840 2020-08-14T02:36:25 Z cheeheng Colors (RMI18_colors) C++14
78 / 100
 1031 ms 63060 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[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);
        }
    }
}

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, p[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 137 ms 19840 KB Output is correct
2 Correct 56 ms 19808 KB Output is correct
3 Correct 23 ms 20052 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 19840 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 19712 KB Output is correct
2 Correct 57 ms 20344 KB Output is correct
3 Correct 21 ms 19968 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 19712 KB Output is correct
2 Correct 57 ms 20344 KB Output is correct
3 Correct 21 ms 19968 KB Output is correct
4 Correct 311 ms 22884 KB Output is correct
5 Correct 584 ms 37356 KB Output is correct
6 Correct 1031 ms 63060 KB Output is correct

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 19840 KB Output is correct
2 Correct 56 ms 19808 KB Output is correct
3 Correct 23 ms 20052 KB Output is correct
4 Correct 137 ms 19712 KB Output is correct
5 Correct 57 ms 20344 KB Output is correct
6 Correct 21 ms 19968 KB Output is correct
7 Correct 137 ms 21240 KB Output is correct
8 Correct 55 ms 20344 KB Output is correct
9 Correct 19 ms 19968 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 281 ms 19712 KB Output is correct
2 Correct 626 ms 38176 KB Output is correct
3 Correct 557 ms 52068 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 19860 KB Output is correct
2 Correct 36 ms 20468 KB Output is correct
3 Correct 24 ms 19968 KB Output is correct

Subtask #8
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 19840 KB Output is correct
2 Correct 56 ms 19808 KB Output is correct
3 Correct 23 ms 20052 KB Output is correct
4 Correct 125 ms 19840 KB Output is correct
5 Correct 137 ms 19712 KB Output is correct
6 Correct 57 ms 20344 KB Output is correct
7 Correct 21 ms 19968 KB Output is correct
8 Correct 311 ms 22884 KB Output is correct
9 Correct 584 ms 37356 KB Output is correct
10 Correct 1031 ms 63060 KB Output is correct
11 Correct 137 ms 21240 KB Output is correct
12 Correct 55 ms 20344 KB Output is correct
13 Correct 19 ms 19968 KB Output is correct
14 Correct 281 ms 19712 KB Output is correct
15 Correct 626 ms 38176 KB Output is correct
16 Correct 557 ms 52068 KB Output is correct
17 Correct 69 ms 19860 KB Output is correct
18 Correct 36 ms 20468 KB Output is correct
19 Correct 24 ms 19968 KB Output is correct
20 Correct 187 ms 22364 KB Output is correct
21 Correct 586 ms 45280 KB Output is correct
22 Incorrect 244 ms 37412 KB Output isn't correct