Submission #1272597

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272597		algoproclub	Colors (RMI18_colors)	C++20	68 / 100	632 ms	113724 KiB

colors

// UUID: 9f8235cf-7184-4e4c-8187-432dea0f2e36

#include <bits/stdc++.h>
 
using namespace std;
 
#ifdef DEBUG
namespace debug {
int dbg_rec = 0;
 
template <typename T, typename... U>
concept IsAnyOf = (std::same_as<T, U> || ...);
 
template<typename T>
concept IsCont = IsAnyOf<T, std::vector<typename T::value_type>, 
std::set<typename T::value_type>,
std::multiset<typename T::value_type>>;
 
template<typename Ostream, IsCont Cont> 
Ostream& operator<<(Ostream& os,  const Cont v){ os<<"["; for(auto& x : v){os<<x<<", ";} os<<"]"; return os; }
 
template<typename Ostream, typename ...Ts>
Ostream& operator<<(Ostream& os,  const pair<Ts...>& p){
    os<<"{"<<p.first<<", "<<p.second<<"}"; return os;
}
 
template<typename T>
void print_dbg(stringstream& ss, T x) { ss << x; }
template<typename T, typename... Args>
void print_dbg(stringstream& ss, T x, Args... args) { ss << x << ", "; print_dbg(ss, args...); }
}
#define dbg(...) {stringstream ss; ++debug::dbg_rec; debug::print_dbg(ss, __VA_ARGS__); --debug::dbg_rec; cerr << string(debug::dbg_rec, '\t') << "\e[91m" << __func__ << ":" << __LINE__ << '\t' << #__VA_ARGS__ << " = " << ss.str() << "\e[39m" << endl; }
#define ASSERT(x) assert((x))
#else
#define dbg(...)
#define ASSERT(x)
#endif
 
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

const int logn = 20;

struct dsu_tree {
    vector<int> p, sz, idx, tree, info, l, r;
    vector<vector<int>> g;
    vector<vector<int>> to;

    dsu_tree(int n, int si) : p(n, -1), sz(n, 1), idx(n), tree(n, -1), info(n, si) {
        iota(all(idx), 0);
    }
    int get(int x) { return p[x] == -1 ? x : p[x] = get(p[x]); } // stash

    bool unio(int a, int b, int x) {
        // cerr << "union: " << a << ' ' << b << '\n';
        a = get(a); b = get(b);
        if(a == b) return false;


        if(sz[a] < sz[b]) swap(a, b);
        // build tree
        int root = new_node(x);
        tree[idx[a]] = root;
        tree[idx[b]] = root;
        idx[a] = root;
        
        sz[a] += sz[b];
        p[b] = a;
        return true;
    }

    int new_node(int x) {
        info.push_back(x);
        tree.push_back(-1);
        return (int)tree.size() - 1;
    }

    int IDX = 0;
    void dfs(int x) {
        if(x < (int)p.size()) { // leaf
            l[x] = r[x] = IDX++;
            return;
        }
        l[x] = 1e9;
        r[x] = -1;
        for(int y : g[x]) {
            dfs(y);
            l[x] = min(l[x], l[y]);
            r[x] = max(r[x], r[y]);
        }
    }

    void calcup() { // all nodes must be connected
        int n = (int)tree.size();
        to.assign(logn, vector<int>(n, n-1));
        for(int i = 0; i < n-1; i++) to[0][i] = tree[i]; // not the root
        for(int j = 1; j < logn; j++) {
            for(int i = 0; i < n; i++) to[j][i] = to[j-1][to[j-1][i]];
        }
        g.assign(n, vector<int>());
        l.resize(n);
        r.resize(n);
        // for(int x : tree) cerr << x << ' ';
        // cerr << endl;
        for(int i = 0; i < n-1; i++) g[tree[i]].push_back(i); // not the root
        IDX = 0;
        dfs(n-1);

        // for(int i = 0; i < n; i++) {
        //     cerr << i << ": " << l[i] << ' ' << r[i] << " | " << info[i] << '\n';
        // }

    }

    int get_up(int x, int maxi){
        for(int j = logn-1; j >= 0; j--) {
            if(info[to[j][x]] < maxi) x = to[j][x]; 
        }
        return x;
    }

    pair<int, int> get_inter(int x, int maxi){
        x = get_up(x, maxi);
        return {l[x], r[x]};
    }
};

void solve() {
     int n, m;
    cin>>n>>m;

    vector<int> a(n), b(n);
    for(int &x : a) cin>>x;
    for(int &x : b) cin>>x;

    vector<vector<int>> g(n);
    for(int i = 0; i < m; i++) {
        int x, y;
        cin>>x>>y;
        --x, --y;
        g[x].push_back(y);
        g[y].push_back(x);
    }

    vector<int> ord(n);
    iota(all(ord), 0);
    
    dsu_tree dsu_a(n, -n - 1);
    dsu_tree dsu_b(n, 0);
    
    vector<bool> used(n, false);
    // A szerinti csökkenően
    {
        sort(all(ord), [&a](int i, int j) { return a[i] > a[j]; });
        for(int i : ord) {
            used[i] = true;
            for(int y : g[i]) {
                if(used[y]) dsu_a.unio(i, y, -a[i]);
            }
        }
        dsu_a.calcup();
    }
    // B szerint növekvően
    {
        used.assign(n, false);
        sort(all(ord), [&b](int i, int j) { return b[i] < b[j]; });
        for(int i : ord) {
            used[i] = true;
            for(int y : g[i]) {
                if(used[y]) dsu_b.unio(i, y, b[i]);
            }
        }
        dsu_b.calcup();
    }

    vector<pair<int, int>> coord(n);
    map<int, vector<int>> colors;
    for(int i = 0; i < n; i++) {
        coord[i] = {dsu_a.l[i], dsu_b.l[i]};
        colors[a[i]].push_back(i);
    }

    for(int i = 0; i < n; i++) {
        auto [lx, rx] = dsu_a.get_inter(i, -b[i] + 1);
        auto [ly, ry] = dsu_b.get_inter(i, b[i] + 1);

        // cerr << "color: " << b[i] << " | " << lx << ' ' << rx << " | " << ly << ' ' << ry << endl;

        // bruteforce:
        bool ok = false;
        for(auto j : colors[b[i]]) {
            auto [x, y] = coord[j];
            if(lx <= x && x <= rx && ly <= y && y <= ry) {
                ok = true;
                break;
            }
        }
        if(!ok){
            cout << 0 << '\n';
            return;
        }
    }
    cout << 1 << '\n';
}

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

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

    return 0;
}

• 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: 0 / 10
• Subtask 8: 0 / 22