Submission #710236

#	Time	Username	Problem	Language	Result	Execution time	Memory
710236		PixelCat	Reconstruction Project (JOI22_reconstruction)	C++14	0 / 100	1 ms	340 KiB

reconstruction

#include <bits/stdc++.h>
#define For(i, a, b) for(int i = a; i <= b; i++)
#define Forr(i, a, b) for(int i = a; i >= b; i--)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define sz(x) ((int)x.size())
#define eb emplace_back
#define int LL
using namespace std;
using LL = long long;
using pii = pair<int, int>;

struct Nyan {
    int ssm, sbg;
    multiset<int> sm, bg;
    int last_qry;
    void init() {
        ssm = sbg = 0;
        sm.clear();
        bg.clear();
        last_qry = 0;
    }
    void insert(int x) {
        if(x <= last_qry) {
            sm.insert(x);
            ssm += x;
        } else {
            bg.insert(x);
            sbg += x;
        }
    }
    void erase(int x) {
        if(x <= last_qry) {
            sm.erase(sm.find(x));
            ssm -= x;
        } else {
            bg.erase(bg.find(x));
            sbg -= x;
        }
    }
    int eval(int x) {
        while(sz(bg) && (*bg.begin()) <= x) {
            int k = *bg.begin();
            ssm += k;
            sbg -= k;
            sm.insert(k);
            bg.erase(bg.begin());
        }
        last_qry = x;
        return x * (sz(sm) - sz(bg)) - ssm + sbg;
    }
} owo;

const int MAXN = 510;
const int MAXM = 100010;

struct Edge {
    int a, b, ab, w;
};

struct Tree {
    int n;
    vector<Edge> te;  // tree edge
    vector<int> adj[MAXN];
    int cc[MAXN];  // connected component
    int d[MAXN];  // depth
    int p[MAXN];  // parent
    void init(int _n) {
        n = _n;
        te.clear();
        rebuild();
    }
    void dfs(int v, int par, int dep, int cid) {
        cc[v] = cid;
        d[v] = dep;
        for(auto &eid:adj[v]) {
            int i = te[eid].ab ^ v;
            if(i != par) {
                p[i] = eid;
                dfs(i, v, dep + 1, cid);
            }
        }
    }
    void rebuild() {
        For(i, 1, n) {
            adj[i].clear();
            cc[i] = -1;
        }
        For(i, 0, sz(te) - 1) {
            adj[te[i].a].eb(i);
            adj[te[i].b].eb(i);
        }
        int num_cc = 0;
        For(i, 1, n) if(cc[i] < 0) {
            num_cc++;
            dfs(i, i, 1, num_cc);
        }
    }
    int climb(int a, int b) {
        pii res(1e18, -1);  // min weight, eid
        auto up = [&](int k) {
            auto &e = te[p[k]];
            res = min(res, pii(e.w, p[k]));
            return e.ab ^ k;
        };
        if(d[a] < d[b]) swap(a, b);
        while(d[a] > d[b]) a = up(a);
        while(a != b) {
            a = up(a); b = up(b);
        }
        return res.S;
    }
    int add_edge(Edge e) {
        if(cc[e.a] != cc[e.b]) {
            te.eb(e);
            rebuild();
            return -1;
        }
        int eid = climb(e.a, e.b);
        int res = te[eid].w;
        te[eid] = e;
        rebuild();
        return res;
    }
    void out() {
        For(i, 1, n) cout << cc[i] << " \n"[i == n];
        for(auto &e:te) cout << e.a << "-" << e.b << " ";
        cout << "\n";
    }
} tr;

Edge ed[MAXM];

int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    // =^-w-^=
    int n, m; cin >> n >> m;
    For(i, 1, m) {
        auto &e = ed[i];
        cin >> e.a >> e.b >> e.w;
        e.ab = e.a ^ e.b;
    }
    sort(ed + 1, ed + m + 1, [&](auto &a, auto &b) {
        return a.w < b.w;
    });
    owo.init();
    tr.init(n);
    // tr.out();
    vector<pair<int, pii>> ev;  // {time, {old, new}}
    For(i, 1, m) {
        auto res = tr.add_edge(ed[i]);
        if(res < 0) owo.insert(ed[i].w);
        else {
            int a = res;
            int b = ed[i].w;
            int mi = b - ((b - a) / 2);
            ev.eb(mi, pii(a, b));
            cout << mi << " " << a << " " << b << "\n";
        }
        // tr.out();
    }
    sort(all(ev));
    reverse(all(ev));
    int q; cin >> q;
    while(q--) {
        int x; cin >> x;
        while(sz(ev) && ev.back().F <= x) {
            auto p = ev.back().S;
            owo.erase(p.F);
            owo.insert(p.S);
            ev.pop_back();
        }
        cout << owo.eval(x) << "\n";
    }
    return 0;
}

• Subtask 1: 0 / 3
• Subtask 2: 0 / 4
• Subtask 3: 0 / 7
• Subtask 4: 0 / 28
• Subtask 5: 0 / 35
• Subtask 6: 0 / 23