oj.uz

Submission #263851

# Submission time Handle Problem Language Result Execution time Memory
263851 2020-08-14T02:39:16 Z cheeheng Colors (RMI18_colors) C++14
78 / 100
 1036 ms 56724 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, 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 123 ms 19712 KB Output is correct
2 Correct 51 ms 19796 KB Output is correct
3 Correct 21 ms 19968 KB Output is correct

Subtask #2
7.0 / 7.0

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

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 19712 KB Output is correct
2 Correct 57 ms 19712 KB Output is correct
3 Correct 18 ms 19968 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 19712 KB Output is correct
2 Correct 57 ms 19712 KB Output is correct
3 Correct 18 ms 19968 KB Output is correct
4 Correct 261 ms 19832 KB Output is correct
5 Correct 636 ms 33232 KB Output is correct
6 Correct 1036 ms 56724 KB Output is correct

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 19712 KB Output is correct
2 Correct 51 ms 19796 KB Output is correct
3 Correct 21 ms 19968 KB Output is correct
4 Correct 147 ms 19712 KB Output is correct
5 Correct 57 ms 19712 KB Output is correct
6 Correct 18 ms 19968 KB Output is correct
7 Correct 127 ms 19796 KB Output is correct
8 Correct 56 ms 19712 KB Output is correct
9 Correct 22 ms 19968 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 240 ms 19712 KB Output is correct
2 Correct 561 ms 33144 KB Output is correct
3 Correct 516 ms 45028 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 32 ms 20184 KB Output is correct
3 Correct 21 ms 19968 KB Output is correct

Subtask #8
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 19712 KB Output is correct
2 Correct 51 ms 19796 KB Output is correct
3 Correct 21 ms 19968 KB Output is correct
4 Correct 124 ms 19840 KB Output is correct
5 Correct 147 ms 19712 KB Output is correct
6 Correct 57 ms 19712 KB Output is correct
7 Correct 18 ms 19968 KB Output is correct
8 Correct 261 ms 19832 KB Output is correct
9 Correct 636 ms 33232 KB Output is correct
10 Correct 1036 ms 56724 KB Output is correct
11 Correct 127 ms 19796 KB Output is correct
12 Correct 56 ms 19712 KB Output is correct
13 Correct 22 ms 19968 KB Output is correct
14 Correct 240 ms 19712 KB Output is correct
15 Correct 561 ms 33144 KB Output is correct
16 Correct 516 ms 45028 KB Output is correct
17 Correct 61 ms 19840 KB Output is correct
18 Correct 32 ms 20184 KB Output is correct
19 Correct 21 ms 19968 KB Output is correct
20 Correct 158 ms 20060 KB Output is correct
21 Correct 555 ms 39252 KB Output is correct
22 Incorrect 232 ms 30204 KB Output isn't correct