Submission #1322268

#	Time	Username	Problem	Language	Result	Execution time	Memory
1322268		phungmanager0	Split the Attractions (IOI19_split)	C++20	18 / 100	76 ms	26164 KiB

split

#include <bits/stdc++.h>
#include "split.h"
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i++)
#define FORD(i, b, a) for (int i = (b), _a = (a); i >= _a; i--)
#define REP(i, n) for (int i = 0, _n = (n); i < _n; i++)
#define FORE(i, v) for (__typeof((v).begin()) i = (v).begin(); i != (v).end(); i++)
#define ALL(v) (v).begin(), (v).end()
using namespace std;

struct DisjointSet {
    vector<int> par, Sz;
    void init(int n) { par.resize(n + 5); Sz.resize(n + 5); 
REP(i, n) par[i] = i, Sz[i] = 1;}
    int get(int u) { return (par[u] == u ? u : par[u] = get(par[u])); }
    bool merge(int u, int v) {
        u = get(u); v = get(v); 
        if(u == v) return false;
        if(Sz[u] < Sz[v]) swap(u, v);
        par[v] = u; Sz[u] += Sz[v];
        return true;
    }
};
struct updateDisjointSet {
    vector<int> par, Sz, total_val; void init(int n) { par.resize(n + 5); Sz.resize(n + 5); total_val.resize(n + 5); 
REP(i, n) par[i] = i, Sz[i] = 1; }
    void update(int idx, int W) { total_val[idx] = W; }
    int get(int u) { return (u == par[u] ? u : par[u] = get(par[u])); }
    void merge(int u, int v) {
        u = get(u); v = get(v); if(u == v) return; if(Sz[u] < Sz[v]) swap(u, v);
        par[v] = u; Sz[u] += Sz[v]; total_val[u] += total_val[v];
    }
};
bool subtaks1(vector<int> p, vector<int> q, int n) {
    vector<int> cnt(n); REP(i, (int)q.size()) { cnt[p[i]]++; cnt[q[i]]++; }
    REP(i, n) if(cnt[i] >= 3) return false;
    return true;
}
bool cmp(const pair<int, int>& a, const pair<int, int>& b) { return a.first < b.first; }
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
    vector<pair<int, int>> cmp_list = {{a, 1}, {b, 2}, {c, 3}}; sort(ALL(cmp_list), cmp);
    //FORE(it, cmp_list) cout << (*it).second << endl;
    DisjointSet dsu, compress; dsu.init(n); compress.init(n);
    vector<int> res(n), h(n), Sz(n); vector<pair<int, int>> edges, edgesspanningtree; REP(i, (int)p.size()) {
        edges.push_back({p[i], q[i]}); //cout << edges.back().first << " " << edges.back().second << endl;
    }
    vector<vector<int>> spanningtree, g; spanningtree.resize(n + 5); g.resize(n + 5); int u = 0, v = 0;
    FORE(it, edges) {
        u = (*it).first; v = (*it).second; if(dsu.merge(u, v)) {
            spanningtree[u].push_back(v); spanningtree[v].push_back(u);
            //cout << u << " " << v << endl;
            edgesspanningtree.push_back({u, v});
        }
        g[u].push_back(v); g[v].push_back(u);
    }
    function<void(int, int)> DFS = [&](int u, int p) {
        Sz[u] = 1;
        FORE(it, spanningtree[u]) if((*it) != p) {
            h[(*it)] = h[u] + 1; DFS((*it), u); Sz[u] += Sz[*it];
        }
    };
    function<int(int, int)> FindCentroid = [&](int u, int p) {
        FORE(it, spanningtree[u]) if((*it) != p && Sz[(*it)] > n / 2) {
            return FindCentroid(*it, u);
        }
        return u;
    };
    DFS(0, -1); int centroid = FindCentroid(0, -1); //cout << centroid << endl;
    FORE(it, edges) {
        if((*it).first != centroid && (*it).second != centroid) {
            compress.merge((*it).first, (*it).second);
        }
    }
    vector<pair<int, int>> points; REP(i, n) if(i == compress.get(i)) {
        points.push_back({i, 0}); //cout << i << endl;
    }
    for(auto &[x, y] : points) y = compress.Sz[compress.get(x)]; int cnt = 0;
    //cout << "debug points: " << "\n"; FORE(it, points) cout << (*it).first << " " << (*it).second << endl;
    function<void(int, int)> DFS_Fill = [&](int u, int p) {
        if(cnt == cmp_list[0].first) return;
        res[u] = cmp_list[0].second; /*cout << "dbg: " << u << endl;*/ cnt++; if(cnt == cmp_list[0].first) return;
        FORE(it, spanningtree[u]) if((*it) != p) {
            if(cnt == cmp_list[0].first) return;
            DFS_Fill(*it, u);
            if(cnt== cmp_list[0].first) return;
        }
    };
    bool check = false; int idx_comp = -1;
    FORE(it, points) {
        if((*it).second >= cmp_list[0].first && (*it).first != centroid) {
            check = true; idx_comp = (*it).first; break; }
    }
    if(check) {
        //cout << "dbg";
        int next_idx = -1; 
        FORE(it, spanningtree[centroid]) if(compress.get(*it) == idx_comp) { next_idx = (*it); break; }
        else if((*it) == idx_comp) { next_idx = idx_comp; break; }
        //cout << "dbg: " << next_idx << endl;
        //cout << idx_comp << endl;
        DFS_Fill(next_idx, centroid); queue<int> q; q.push(centroid); cnt = 0; while(q.size()) {
            int u = q.front(); q.pop(); cnt++; res[u] = cmp_list[1].second;
            //cout << "debug bfs: " << u << endl;
            if(cnt == cmp_list[1].first) break;
            FORE(it, spanningtree[u]) if(res[*it] == 0) {
                q.push(*it);// cout << "debug bfs: " << (*it) << endl;
            }
        }
        REP(i, n) if(res[i] == 0) res[i] = cmp_list[2].second;
    } else {
        updateDisjointSet compute; compute.init(n);
        // compress is a forest
        REP(i, (int)points.size()) compute.update(points[i].first, points[i].second);
        vector<vector<int>> newGraph(n + 1); vector<int> Weight(n + 1);
        FORE(it, points) Weight[(*it).first] = (*it).second;
        int first_comp = -1, second_comp = -1;
        FORE(it, edges) {
            first_comp = compress.get((*it).first); second_comp = compress.get((*it).second);
            if(first_comp != second_comp) {
                newGraph[first_comp].push_back(second_comp); newGraph[second_comp].push_back(first_comp);
                compute.merge(first_comp, second_comp);
                //cout << "debug spanning tree: " << (*it).first << " " << (*it).second << endl;
            }
            //cout << "debug spanning tree: " << (*it).first << " " << (*it).second << endl;
        }
        bool check_ans = false; int start_bfs = 0; vector<bool> check(n + 1), allow(n + 1);
        FORE(it, points) if(compute.total_val[compute.get((*it).first)] >= cmp_list[0].first) { check_ans = true; start_bfs = (*it).first; break; }
        if(check_ans) {
            //cout << "dbg";
            queue<int> q; int sumWeight = 0;
            q.push(start_bfs); while(q.size()) {
                int u = q.front(); check[u] = true; q.pop();
                sumWeight += Weight[u]; if(sumWeight >= cmp_list[0].first) break;
                else {
                    FORE(it, newGraph[u]) if(!check[(*it)]) q.push(*it);
                }
            }
            REP(i, n) if(check[compress.get(i)]) allow[i] = true;
            while(q.size()) q.pop(); q.push(start_bfs); int cnt = 0; while(q.size()) {
                int u = q.front(); res[u] = cmp_list[0].second; cnt++; q.pop(); if(cnt == cmp_list[0].first) break;
                else {
                    FORE(it, g[u]) if(res[*it] == 0 && allow[*it]) q.push(*it);
                }
            } while(q.size()) q.pop(); q.push(centroid); cnt = 0; while(q.size()) {
                int u = q.front(); q.pop(); cnt++; res[u] = cmp_list[1].second;
                if(cnt == cmp_list[1].first) break;
                FORE(it, spanningtree[u]) if(res[*it] == 0) {
                    q.push(*it);
                }
            }
            REP(i, n) if(res[i] == 0) res[i] = cmp_list[2].second;
        }
    }
    //cout << "dbg";
    return res;
}

• Subtask 1: 7 / 7
• Subtask 2: 11 / 11
• Subtask 3: 0 / 22
• Subtask 4: 0 / 24
• Subtask 5: 0 / 36