Submission #1146431

#	Time	Username	Problem	Language	Result	Execution time	Memory
1146431		Zero_OP	Colors (RMI18_colors)	C++20	100 / 100	378 ms	90084 KiB

colors

#include <bits/stdc++.h>

using namespace std;

#define mp make_pair
#define rep(i, l, r) for(int i = (l); i < (r); ++i)
#define all(v) begin(v), end(v)
#define rall(v) rbegin(v), rend(v)
#define compact(v) v.erase(unique(all(v)), end(v))
#define sz(v) (int)v.size()
#define dbg(x) "[" #x " = " << (x) << "]"
#define file(task) if(fopen(task".inp", "r")){ freopen(task".inp", "r", stdin); freopen(task".out", "w", stdout); }

template<typename T>
bool minimize(T& a, const T& b){
    if(a > b) return a = b, true;
    return false;
}

template<typename T>
bool maximize(T& a, const T& b){
    if(a < b) return a = b, true;
    return false;
}

using ll = long long;
using ull = unsigned long long;
using ld = long double;
using vi = vector<int>;
using vl = vector<ll>;

using pi = pair<int, int>;
using vpi = vector<pi>;
using vb = vector<bool>;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

const int MAX = 2e5 + 5;

int N, M, a[MAX], b[MAX];
pi e[MAX];

namespace Solver{

    struct DSU_Rollback{
        vi lab;
        vb ok;
        stack<tuple<int, int, int, int>> st;
        DSU_Rollback(int n) : lab(n, -1), ok(n, false), st() {}

        int root(int u){
            return lab[u] < 0 ? u : (root(lab[u]));
        }

        bool join(int u, int v){
            u = root(u);
            v = root(v);
            if(u == v) return false;
            if(lab[u] > lab[v]) swap(u, v);
            st.push(make_tuple(u, lab[u], v, lab[v]));
            lab[u] += lab[v];
            lab[v] = u;
            return true;
        }

        void update(int u, bool v){
            u = root(u);
            ok[u] = v;
        }

        int snapshot(){ return sz(st); }
        void rollback(int snap){
            assert(snap <=   snapshot());
            while(snap != snapshot()){
                int u, labu, v, labv;
                tie(u, labu, v, labv) = st.top();
                st.pop();
                lab[u] = labu;
                lab[v] = labv;
            }
        }

        bool get_ok(int u){ return ok[root(u)]; }
    } dsu(0);

    vi valid[MAX * 4], check[MAX * 4], events[MAX * 4];

    void init(int n){
        dsu = DSU_Rollback(n);
        rep(i, 1, 4 * n){
            events[i].clear();
            if(i <= n) valid[i].clear(), check[i].clear();
        }
    }

    void add_valid(int x, int id){
        valid[x].emplace_back(id);
    }

    void add_check(int x, int id){
        check[x].emplace_back(id);
    }

    void add_edge(int id, int l, int r, int u, int v, int e){
        if(u <= l && r <= v) events[id].emplace_back(e);
        else{
            int mid = l + r >> 1;
            if(u <= mid) add_edge(id << 1, l, mid, u, v, e);
            if(mid < v)  add_edge(id << 1 | 1, mid + 1, r, u, v, e);
        }
    }

    bool solve(int id, int l, int r){
        int pre = dsu.snapshot();
        for(auto i : events[id]){
            dsu.join(e[i].first, e[i].second);
        }

        if(l == r){
            for(auto x : valid[l]) dsu.update(x, true);
            for(auto x : check[l]) {
                if(!dsu.get_ok(x)) {
                    return false;
                }
            }
            for(auto x : valid[l]) dsu.update(x, false);
        } else{
            int mid = l + r >> 1;
            if(!solve(id << 1, l, mid)) return false;
            if(!solve(id << 1 | 1, mid + 1, r)) return false;
        }

        dsu.rollback(pre);
        return true;
    }
}

void testcase(){
    cin >> N >> M;
    rep(i, 0, N) cin >> a[i];
    rep(i, 0, N) cin >> b[i];

    rep(i, 0, M){
        int u, v;
        cin >> u >> v;
        --u, --v;
        e[i] = {u, v};
    }

    rep(i, 0, N){
        if(a[i] < b[i]){
            cout << 0 << '\n';
            return;
        }
    }

    Solver::init(N);
    rep(i, 0, N){
        Solver::add_valid(a[i], i);
        Solver::add_check(b[i], i);
    }

    rep(i, 0, M){
        int u, v; tie(u, v) = e[i];

        int l = max(b[u], b[v]);
        int r = min(a[u], a[v]);
        if(l <= r){
            Solver::add_edge(1, 1, N, l, r, i);
        }
    }

    cout << Solver::solve(1, 1, N) << '\n';
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

#ifdef LOCAL
    freopen("task.inp", "r", stdin);
    freopen("task.out", "w", stdout);
#endif // LOCAL

    int t;
    cin >> t;
    while(t--) testcase();

    return 0;
}

/*

Subtask 1 :

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

3 3
1 2 3
1 1 2
1 2
2 3
3 1

*/

• 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