Submission #1144070

#	Time	Username	Problem	Language	Result	Execution time	Memory
1144070		Mike_Vu	Colors (RMI18_colors)	C++17	38 / 100	167 ms	27668 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 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)];
    }
};

const int maxn = 15e4+5;
int n, m, a[maxn], b[maxn];
vector<int> adj[maxn], posa[maxn], posb[maxn];
DSU dsu;
bool ans, act[maxn];

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++) {
        adj[i].clear();
        posa[i].clear();
        posb[i].clear();
        act[i] = 0;
    }
    ans = 1;
    //input, getval
    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);
    }
    //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 (!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);
        }
    }
}

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--) {
        cin >> n >> m;
        solve();
        cout << ans << "\n";
//        cout << endl;
    }
}
/*
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: 16 / 16
• Subtask 7: 0 / 10
• Subtask 8: 0 / 22