oj.uz

Submission #262763

# Submission time Handle Problem Language Result Execution time Memory
262763 2020-08-13T08:32:23 Z dantoh000 Colors (RMI18_colors) C++14
78 / 100
 893 ms 106736 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef pair<int,int> ii;
int n,m;
int A[150005];
int B[150005];
int U[150005];
int V[150005];
int has[150005];
vector<int> source[150005];
vector<int> sink[150005];
int ans = 0;
struct UFDS{
    vector<ii> op;
    int p[150005];
    int sz[150005];
    void init(int n){
        for (int i = 1 ; i <= n; i++){
            p[i] = i;
            sz[i] = 1;
        }
    }
    int find(int x){
        return x == p[x] ? x : find(p[x]);
    }
    void un(int x, int y){
        x = find(x), y = find(y);
        if (x == y) return;
        if (sz[x] < sz[y]) swap(x,y);
        p[y] = x;
        sz[x] += sz[y];
        op.push_back({x,y});
    }
    void roll(int SZ){
        int x,y;
        while (op.size() > SZ){
            tie(x,y) = op.back(); op.pop_back();
            sz[x] -= sz[y];
            p[y] = y;
        }
    }
} ufds;
struct node{
    int s,e,m;
    vector<ii> V;
    node *l, *r;
    node (int _s, int _e): s(_s), e(_e){
        m = (s+e)/2;
        if (s != e){
            l = new node(s,m);
            r = new node(m+1,e);
        }
    }
    void up(int qs ,int qe, ii v){
        if (qs == s && qe == e){
            V.push_back(v);
            return;
        }
        if (qs > m) r->up(qs,qe,v);
        else if (qe<=m) l->up(qs,qe,v);
        else l->up(qs,m,v), r->up(m+1,qe,v);
    }
    void dfs(){
        int oldsz = ufds.op.size();
        for (auto x : V){
            ufds.un(x.fi,x.se);
        }
        if (s == e){
            for (auto x : source[s]){
                has[ufds.find(x)] = 1;
            }
            for (auto x : sink[s]){
                if (!has[ufds.find(x)]) ans = 0;
            }
            for (auto x : source[s]){
                has[ufds.find(x)] = 0;
            }
        }
        else{
            l->dfs();
            r->dfs();
        }
        ufds.roll(oldsz);
    }
} *root;
int main(){
    int TC;
    scanf("%d",&TC);
    while (TC--){
        ans = 1;
        scanf("%d%d",&n,&m);
        root = new node(1,n);
        ufds.init(n);
        for (int i = 1; i <= n; i++){
            source[i].clear();
            sink[i].clear();
        }
        for (int i = 1; i <= n; i++) {
            scanf("%d",&A[i]);
            source[A[i]].push_back(i);
        }
        for (int i = 1; i <= n; i++) {
            scanf("%d",&B[i]);
            sink[B[i]].push_back(i);
        }
        for (int i = 1; i <= m; i++) {
            scanf("%d%d",&U[i],&V[i]);
            int L = max(B[U[i]],B[V[i]]);
            int R = min(A[U[i]],A[V[i]]);
            if (L > R) continue;
            root->up(L,R,ii(U[i],V[i]));
        }
        root->dfs();
        printf("%d\n",ans);
    }

}

Compilation message

colors.cpp: In member function 'void UFDS::roll(int)':
colors.cpp:38:26: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   38 |         while (op.size() > SZ){
      |                ~~~~~~~~~~^~~~
colors.cpp: In function 'int main()':
colors.cpp:90:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   90 |     scanf("%d",&TC);
      |     ~~~~~^~~~~~~~~~
colors.cpp:93:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   93 |         scanf("%d%d",&n,&m);
      |         ~~~~~^~~~~~~~~~~~~~
colors.cpp:101:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  101 |             scanf("%d",&A[i]);
      |             ~~~~~^~~~~~~~~~~~
colors.cpp:105:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  105 |             scanf("%d",&B[i]);
      |             ~~~~~^~~~~~~~~~~~
colors.cpp:109:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  109 |             scanf("%d%d",&U[i],&V[i]);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 31096 KB Output is correct
2 Correct 46 ms 15992 KB Output is correct
3 Correct 10 ms 8448 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 17016 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 31736 KB Output is correct
2 Correct 52 ms 16120 KB Output is correct
3 Correct 12 ms 8576 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 31736 KB Output is correct
2 Correct 52 ms 16120 KB Output is correct
3 Correct 12 ms 8576 KB Output is correct
4 Correct 278 ms 58232 KB Output is correct
5 Correct 560 ms 85012 KB Output is correct
6 Correct 893 ms 106736 KB Output is correct

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 31096 KB Output is correct
2 Correct 46 ms 15992 KB Output is correct
3 Correct 10 ms 8448 KB Output is correct
4 Correct 131 ms 31736 KB Output is correct
5 Correct 52 ms 16120 KB Output is correct
6 Correct 12 ms 8576 KB Output is correct
7 Correct 138 ms 31480 KB Output is correct
8 Correct 49 ms 15992 KB Output is correct
9 Correct 11 ms 8576 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 256 ms 57244 KB Output is correct
2 Correct 535 ms 84676 KB Output is correct
3 Correct 555 ms 82396 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 12792 KB Output is correct
2 Correct 23 ms 9472 KB Output is correct
3 Correct 13 ms 8576 KB Output is correct

Subtask #8
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 31096 KB Output is correct
2 Correct 46 ms 15992 KB Output is correct
3 Correct 10 ms 8448 KB Output is correct
4 Correct 117 ms 17016 KB Output is correct
5 Correct 131 ms 31736 KB Output is correct
6 Correct 52 ms 16120 KB Output is correct
7 Correct 12 ms 8576 KB Output is correct
8 Correct 278 ms 58232 KB Output is correct
9 Correct 560 ms 85012 KB Output is correct
10 Correct 893 ms 106736 KB Output is correct
11 Correct 138 ms 31480 KB Output is correct
12 Correct 49 ms 15992 KB Output is correct
13 Correct 11 ms 8576 KB Output is correct
14 Correct 256 ms 57244 KB Output is correct
15 Correct 535 ms 84676 KB Output is correct
16 Correct 555 ms 82396 KB Output is correct
17 Correct 53 ms 12792 KB Output is correct
18 Correct 23 ms 9472 KB Output is correct
19 Correct 13 ms 8576 KB Output is correct
20 Correct 146 ms 22304 KB Output is correct
21 Correct 523 ms 75884 KB Output is correct
22 Incorrect 794 ms 104996 KB Output isn't correct