Submission #1146320

#	Time	Username	Problem	Language	Result	Execution time	Memory
1146320		Mike_Vu	Colors (RMI18_colors)	C++17	100 / 100	390 ms	72504 KiB

colors

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double dou;
#define pii pair<int, int>
#define fi first
#define se second
#define pb push_back
#define BITJ(x, j) (((x)>>(j))&1)
#define MASK(j) (1LL<<(j))
#define ALL(v) v.begin(), v.end()

template<typename T> bool maximize(T &x, const T &y) {
    if (x < y) {x = y; return 1;}
    return 0;
}
template<typename T> bool minimize(T &x, const T &y) {
    if (x > y) {x = y; return 1;}
    return 0;
}

struct BIT{
    int n;
    vector<int> bit;
    void init(int _n = 0) {
        n = _n;
        bit.assign(n+1, 0);
    }
    void update(int k, int x){
        while (k <= n) {
            bit[k] += x;
            k += k & (-k);
        }
    }
    int getsum(int k) {
        int res = 0;
        while (k > 0) {
            res += bit[k];
            k -= k & (-k);
        }
        return res;
    }
    int query(int l, int r) {
        return getsum(r)-getsum(l-1);
    }
};

const int maxn = 15e4+5, lg = 18;
int n, m, a[maxn], b[maxn];
vector<int> posa[maxn], posb[maxn];
vector<pii> edges;
bool ans;
bool act[maxn];

void input() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        posa[i].clear();
        posb[i].clear();
    }
    edges.clear();
    for (int i= 1; i <= n; i++) {
        cin >> a[i];
        posa[a[i]].pb(i);
    }
    for (int i = 1; i <= n; i++) {
        cin >> b[i];
        posb[b[i]].pb(i);
    }
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        edges.pb({u, v});
    }
}

namespace full{
    void unite(int &l, int &r, int l2, int r2) {
        minimize(r, r2);
        maximize(l, l2);
    }
    struct DSU{
        int n;
        vector<int> dsu, sz;
        void init(int _n) {
            n = _n;
            dsu.assign(n+1, 0);
            sz.assign(n+1, 1);
            iota(ALL(dsu), 0);
        }
        int f(int u) {
            while (u != dsu[u]) u = dsu[u];
            return u;
        }
        bool join(int u, int v, pii &change) {
            u = f(u);
            v = f(v);
            if (u == v) return 0;
            if (sz[u] < sz[v]) swap(u, v);
            change = make_pair(u, v);
            dsu[v] = u;
            sz[u] += sz[v];
            return 1;
        }
        void revert(pii change) {
            int u = change.fi, v = change.se;
            dsu[v] = v;
            sz[u] -= sz[v];
        }
    };
    DSU dsu;
    void solveval(int x) {
        for (int u : posa[x]) {
            act[dsu.f(u)] = 1;
        }
        for (int u : posb[x]) {
            if (!act[dsu.f(u)]) {
                ans &= 0;
            }
        }
        for (int u : posa[x]) {
            act[dsu.f(u)] = 0;
        }
    }
    namespace tree{
        int trsz, _n;
        vector<vector<pii>> tr;
        void init(int n) {
            trsz = 1;
            _n = n;
            while (trsz < n) trsz <<= 1;
            tr.assign(trsz<<1, vector<pii>());
            dsu.init(n);
        }
        void update(int l, int r, pii edge) {
            l += trsz-1;
            r += trsz;
            while (l < r) {
                if (l&1) tr[l++].pb(edge);
                if (r&1) tr[--r].pb(edge);
                l >>= 1;
                r >>= 1;
            }
        }
        void dfs(int id = 1) {
            vector<pii> cur;
            for (pii e : tr[id]) {
                pii change;
                if (dsu.join(e.fi, e.se, change)) {
                    cur.pb(change);
                }
            }
            if (id >= trsz && id-trsz+1 <= _n) {
                solveval(id-trsz+1);
            }
            if (id < trsz) {
                dfs(id<<1);
                dfs(id<<1|1);
            }
            for (pii change : cur) {
                dsu.revert(change);
            }
        }
    }
    void solve() {
        for (int i = 1; i <= n; i++) {
            act[i] = 0;
            if (a[i] < b[i]) {
                ans = 0;
                return;
            }
            if (posa[i].empty() && !posb[i].empty()) {
                ans = 0;
                return;
            }
        }
        //edges for tree
        tree::init(n);
        for (pii e : edges) {
            int u = e.fi, v = e.se;
            int l = b[u], r = a[u];
            unite(l, r, b[v], a[v]);
//            cout << u << ' ' << v << ' ' << l << ' ' << r << "\n";
            if (l <= r) {
                tree::update(l, r, e);
            }
        }
        tree::dfs();
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
//    #define name "task"
//    if (fopen(name".inp", "r")) {
//        freopen(name".inp", "r", stdin);
//        freopen(name".out", "w", stdout);
//    }
    int t;
    cin >> t;
//    while (cin >> n >> m) {
    while (t--) {
        input();
        ans = 1;
//        trau::solve();
        full::solve();
        cout << ans << "\n";
//        cout << endl;
    }
}
/*
2
4 4
3 3 2 1
2 1 2 1
1 2
2 3
3 4
4 2
4 4
3 3 2 1
1 2 2 1
1 2
2 3
3 4
4 2
*/

• 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