Submission #1146093

#	Time	Username	Problem	Language	Result	Execution time	Memory
1146093		Mike_Vu	Colors (RMI18_colors)	C++17	22 / 100	149 ms	25416 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> adj[maxn], posa[maxn], posb[maxn];
bool ans;
bool act[maxn];

void input() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        adj[i].clear();
        posa[i].clear();
        posb[i].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;
        adj[u].pb(v);
        adj[v].pb(u);
    }
}

namespace trau{
    struct DSU{
        int n;
        vector<int> dsu;
        vector<bool> val;
        void init(int _n) {
            n = _n;
            dsu.assign(n+1, -1);
            val.assign(n+1, 0);
        }
        int f(int u) {
            return dsu[u] < 0 ? u : dsu[u] = f(dsu[u]);
        }
        bool join(int u, int v) {
            u = f(u);
            v = f(v);
            if (u == v) return 0;
            if (dsu[u] > dsu[v]) swap(u, v);
            dsu[u] += dsu[v];
            dsu[v] = u;
            val[u] = val[u]|val[v];
            return 1;
        }
        void turn(int u, bool x) {
            val[f(u)] = x;
        }
        bool fval(int u) {
            return val[f(u)];
        }
    };
    DSU dsu;
    void addnode(int u) {
        act[u] = 1;
        for (int v : adj[u]) {
            if (act[v]) {
                dsu.join(u, v);
            }
        }
    }
    void solve() {
        //clear
        for (int i = 1; i <= n; i++) {
            act[i] = 0;
        }
        //dsu 1
        dsu.init(n);
        for (int i = n; i; i--) {
            if (posa[i].empty() && !posb[i].empty()) {
                ans = 0;
                return;
            }
            for (int u : posa[i]) {
                addnode(u);
            }
            for (int u : posa[i]) {
                dsu.turn(u, 1);
            }
            for (int u : posb[i]) {
                if (!act[u] || !dsu.fval(u)) {
                    ans = 0;
                    return;
                }
            }
            for (int u : posa[i]) {
                dsu.turn(u, 0);
            }
        }
        //dsu 2
        dsu.init(n);
        for (int i= 1; i <= n; i++) {
            act[i] = 0;
        }
        for (int i = 1; i <= n; i++) {
            for (int u : posb[i]) {
                addnode(u);
            }
            for (int u : posa[i]) {
                dsu.turn(u, 1);
            }
            for (int u : posb[i]) {
                if (!dsu.fval(u)) {
                    ans = 0;
                    return;
                }
            }
            for (int u : posa[i]) {
                dsu.turn(u, 0);
            }
        }
    }
}

namespace full{
    int lab[maxn];
    vector<int> tradja[maxn], tradjb[maxn], qu[maxn], nadj[maxn];
    BIT bit;
    int cornodeb[maxn], cornodea[maxn];//save the corresponding ancestor for each b
    int par[maxn][lg], h[maxn];
    int tinb[maxn], toutb[maxn], timer, tina[maxn], touta[maxn], sz[maxn], heavy[maxn], nodeti[maxn];
    bool vis[maxn];
    namespace dsutree{
        void init() {
            for (int i = 1; i <= n; i++) {
                lab[i] = -1;
                act[i] = 0;
            }
        }
        int f(int u) {
            return lab[u] < 0 ? u : lab[u] = f(lab[u]);
        }
        void addnode(int u, vector<int> tradj[]) {
            act[u] = 1;
            for (int v : adj[u]) {
                if (act[v]) {
                    int nv = f(v);
                    if (u == nv) continue;
                    lab[nv] = u;
                    tradj[u].pb(nv);
                }
            }
        }
    }
    void dfsp1(int u) {
        act[u] = 1;
        for (int j = 1; j < lg; j++) {
            if (MASK(j) >= h[u]) break;
            par[u][j] = par[par[u][j-1]][j-1];
        }
        tina[u] = ++timer;
        nodeti[timer] = u;
//        cout << u << ' ' << h[u] << ' ' << par[u][0] << endl;
        for (int v : tradja[u]) {
            if (act[v]) continue;
//            cout << "edge 1 " << u << ' ' << v << "\n";
            h[v] = h[u]+1;
            par[v][0] = u;
            dfsp1(v);
        }
        touta[u] = timer;
    }
    void dfsp2(int u) {
//        cout << u << endl;
        act[u] = 1;
        tinb[u] = ++timer;
        for (int v : tradjb[u]) {
            if (act[v]) continue;
//            cout << "edge 2 " << u << ' ' << v << "\n";
            dfsp2(v);
        }
        toutb[u] = timer;
    }
    int lca(int u, int v) {
        if (h[u] < h[v]) swap(u, v);
        if (h[u] != h[v]) {
            int k = h[u]-h[v];
            for (int j = 0; j < lg; j++) {
                if (BITJ(k, j)) {
                    u = par[u][j];
                }
            }
        }
        if (u == v) return u;
        for (int j = lg-1; j >= 0; j--) {
            while (h[u] > MASK(j) && par[u][j] != par[v][j]){
                u = par[u][j];
                v = par[v][j];
            }
        }
        return par[u][0];
    }
    bool cmpnode(int u, int v) {
        return tina[u] < tina[v];
    }
    void swit(int u, int x) {
//        cout << u << ' ' << tinb[u] << ' ' << x << "\n";
        bit.update(tinb[u], x);
    }
    void dfsprep(int u) {
        vis[u] = 1;
        sz[u] = 1;
        heavy[u] = -1;
        for (int v : nadj[u]) {
            dfsprep(v);
            sz[u] += sz[v];
            if (heavy[u] == -1 || sz[v] > sz[heavy[u]]) {
                heavy[u] = v;
            }
        }
    }
    void dfssolve(int u, bool del) {
        vis[u] = 1;
        //light
        for (int v : nadj[u]) {
            if (v == heavy[u]) continue;
            dfssolve(v, 1);
        }
        //heavy
        if (heavy[u] != -1) dfssolve(heavy[u], 0);
        //light
        for (int v : nadj[u]) {
            if (v == heavy[u]) continue;
            for (int i = tina[v]; i <= touta[v]; i++) {
                if (act[nodeti[i]]) swit(nodeti[i], 1);
            }
        }
        //u
        if (act[u]) swit(u, 1);
        //solve query
        for (int v : qu[u]) {
//            cout << "query " << v << ' ' << tinb[v] << ' ' << toutb[v] << ' ' << bit.query(tinb[v], toutb[v]) << "\n";
            if (bit.query(tinb[v], toutb[v]) == 0) {
                ans &= 0;
            }
        }
        //del
        if (del) {
            for (int i = tina[u]; i <= touta[u]; i++) {
                if (act[nodeti[i]]) swit(nodeti[i], -1);
            }
        }
    }
    void virsolve(vector<int> &nodea, vector<int> &nodeb){
        vector<int> nodes;
        //build nodes
        for (int u : nodea) {
            nodes.pb(u);
            act[u] = 1;
        }
        for (int u : nodeb) {
            nodes.pb(u);
            qu[cornodea[u]].pb(cornodeb[u]);
        }
        sort(ALL(nodes), cmpnode);
        int k = (int)nodes.size();
        for (int i =1; i < k; i++) {
//            cout << nodes[i] << ' ' << nodes[i-1] << ' ' << lca(nodes[i], nodes[i-1]) << endl;
            nodes.pb(lca(nodes[i], nodes[i-1]));
        }
//        system("pause");
        sort(ALL(nodes), cmpnode);
        nodes.erase(unique(ALL(nodes)), nodes.end());
        //build edges
        vector<int> stk;
        stk.pb(nodes[0]);
        k = nodes.size();
        for (int i = 1; i < k; i++) {
            int p = stk.back(), u = nodes[i];
            while (tina[p] > tina[u] || touta[p] < touta[u]) {
                stk.pop_back();
                p = stk.back();
            }
//            cout << p << ' ' << u << "\n";
            nadj[p].pb(u);
        }
//        system("pause");
        //sack on tree + solve
        for (int u : nodes) {
            if (!vis[u]) {
                dfsprep(u);
            }
        }
        for (int u : nodes) {
            vis[u] = 0;
        }
//        system("pause");
        for (int u : nodes) {
            if (!vis[u]) {
                dfssolve(u, 1);
            }
        }
//        system("pause");
        //reset
        for (int u : nodes) {
            nadj[u].clear();
            qu[u].clear();
            act[u] = vis[u] = 0;
        }
    }
    void solve() {
        //clear
        for (int i = 1; i <= n ;i++) {
            tradjb[i].clear();
            tradja[i].clear();
            qu[i].clear();
        }
        ///check special case
        //tree b
        dsutree::init();
        //add
        for (int i = 1; i <= n; i++) {
            if (posa[i].empty() && !posb[i].empty()) {
                ans = 0;
                return;
            }
            for (int u : posb[i]) {
                dsutree::addnode(u, tradjb);
            }
            for (int u : posb[i]) {
                if (b[u] > a[u]) {//must be in the active nodes
                    ans = 0;
//                    cout << "i am here :D\n";
                    return;
                }
                int nu = dsutree::f(u);
                cornodeb[u] = nu;
            }
        }
        //take root -> vector
        //prep euler tour tree b
        for (int i = 1; i <= n; i++) {
            act[i] = 0;
        }
        timer = 0;
        for (int i = 1; i <= n; i++) {
            int u = dsutree::f(i);
            if (!act[u]) {
                dfsp2(u);
            }
        }
        //tree a
        dsutree::init();
        //add
        for (int i= n; i; i--) {
            for (int u : posa[i]) {
                dsutree::addnode(u, tradja);
            }
            for (int u : posb[i]) {
                int nu = dsutree::f(u);
                cornodea[u] = nu;
            }
        }
        //take root -> array
        //prep lca tree a
        for (int i = 1; i <= n; i++) {
            act[i] = 0;
        }
        timer = 0;
        for (int i = 1; i <= n; i++) {
            //reset state
            int u = dsutree::f(i);
            if (!act[u]) {
                h[u] = 1;
                dfsp1(u);
            }
        }
        //reset state
        for (int i = 1; i <= n; i++) {
            act[i] = 0;
        }
        bit.init(n);
        //virtual tree for each lvl
        for (int i = n; i; i--) {
            if (posb[i].empty()) continue;
//            cout << i << endl;
//            system("pause");
            virsolve(posa[i], posb[i]);
        }
    }
}

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;
    }
}
/*
1
7 9
1 2 3 1 2 2 1
1 2 3 1 2 2 1
4 7
1 6
3 7
5 7
1 5
3 4
1 4
1 3
2 7

1
4 4
3 3 2 1
1 2 2 1
1 2
2 3
3 4
4 2

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: 0 / 8
• Subtask 4: 0 / 15
• Subtask 5: 0 / 7
• Subtask 6: 0 / 16
• Subtask 7: 0 / 10
• Subtask 8: 0 / 22