Submission #262770

#	Time	Username	Problem	Language	Result	Execution time	Memory
262770		dantoh000	Colors (RMI18_colors)	C++14	100 / 100	880 ms	99764 KiB

colors

#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[200005];
int V[200005];
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){
        op.clear();
        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 (stderr)

colors.cpp: In member function 'void UFDS::roll(int)':
colors.cpp:39: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]
   39 |         while (op.size() > SZ){
      |                ~~~~~~~~~~^~~~
colors.cpp: In function 'int main()':
colors.cpp:91:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   91 |     scanf("%d",&TC);
      |     ~~~~~^~~~~~~~~~
colors.cpp:94:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   94 |         scanf("%d%d",&n,&m);
      |         ~~~~~^~~~~~~~~~~~~~
colors.cpp:102:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  102 |             scanf("%d",&A[i]);
      |             ~~~~~^~~~~~~~~~~~
colors.cpp:106:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  106 |             scanf("%d",&B[i]);
      |             ~~~~~^~~~~~~~~~~~
colors.cpp:110:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  110 |             scanf("%d%d",&U[i],&V[i]);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~

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