Submission #1274633

#	Time	Username	Problem	Language	Result	Execution time	Memory
1274633		Icelast	Reconstruction Project (JOI22_reconstruction)	C++20	100 / 100	206 ms	17984 KiB

reconstruction

#include <iostream>
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn = 2*1e5+5, INF = 1e9+9;
const int inf = 1.1e9;
struct weightedDSU {

    vector<int> p, pr, wg;

    weightedDSU(int n) : p(n), pr(n), wg(n, inf) {
        for (int i = 0; i < n; i++) p[i] = pr[i] = i;
        mt19937 mt((size_t)make_unique<char>().get());
        shuffle(begin(pr), end(pr), mt);
    }

    int &par(int v) {
        if (p[v] == v) return p[v];
        while (wg[p[v]] <= wg[v]) p[v] = p[p[v]];
        return p[v];
    }
    int find(int v, int w = inf - 1) {
        while (wg[v] <= w) v = par(v);
        return v;
    }
    bool same(int u, int v){
        return find(u) == find(v);
    }
    void add_edge(int u, int v, int w) {
        while (u != v) {
            u = find(u, w), v = find(v, w);
            if (pr[u] < pr[v]) swap(u, v);
            swap(par(v), u), swap(wg[v], w);
        }
    }
    void delete_edge(int v) { par(v) = v, wg[v] = inf; }

    int max_edge(int u, int v) { //THIS RETURNS THE VERTEX
        if (find(u) != find(v)) return -1;
        for (;; u = par(u)) {
            if (wg[u] > wg[v]) swap(u, v);
            if (par(u) == v) return u;
        }
    }
    int max_w(int u, int v) { //THIS RETURNS THE WEIGHT
        return wg[max_edge(u, v)];
    }
    void merge(int u, int v, int w) { //main function to use
        if (u == v) return;
        int id = max_edge(u, v);
        if (id == -1) {
            add_edge(u, v, w);
        } else if (wg[id] > w) {
            delete_edge(id), add_edge(u, v, w);
        }
    }
};
int sgn(int x) {
    if (x == 0) return 0;
    return x < 0 ? -1 : +1;
}
struct edge{
    int u, v, w;
};
void solve(){
    int n, m;
    cin >> n >> m;
    vector<edge> e(m+1);
    for(int i = 1; i <= m; i++){
        int u, v, w;
        cin >> u >> v >> w;
        e[i] = {u, v, w};
    }
    sort(e.begin()+1, e.end(), [&](edge a, edge b){return a.w < b.w;});
    vector<array<int, 2>> event_l = [&]{
        vector<array<int, 2>> events;
        weightedDSU dsu(n+1);
        for(int i = 1; i <= m; i++){
            int u = e[i].u, v = e[i].v, w = e[i].w;
            if(dsu.same(u, v)){
                int ww = dsu.max_w(u, v);
                ww = -ww;
                if(ww != w){
                    events.push_back({(ww + w) / 2 + 1, +w});
                    events.push_back({w + 1, -w});
                }
            }else{
                events.push_back({0, +w});
                events.push_back({w + 1, -w});
            }
            dsu.merge(u, v, -w);
        }
        sort(events.begin(), events.end());
        return events;
    }();

    vector<array<int, 2>> event_r = [&]{
        vector<array<int, 2>> events;
        weightedDSU dsu(n+1);
        for(int i = m; i >= 1; i--){
            int u = e[i].u, v = e[i].v, w = e[i].w;
            if(dsu.same(u, v)){
                int ww = dsu.max_w(u, v);
                events.push_back({w, +w});
                events.push_back({(ww + w) / 2 + 1, -w});
            }else{
                events.push_back({w, +w});
                events.push_back({INF, -w});
            }
            dsu.merge(u, v, w);
        }
        sort(events.begin(), events.end());
        return events;
    }();
    int pl = 0, pr = 0;
    ll suml = 0, sumr = 0;
    ll cntl = 0, cntr = 0;
    int q;
    cin >> q;
    for(int i = 1; i <= q; i++){
        int x;
        cin >> x;
        while(pl < (int)event_l.size() && event_l[pl][0] <= x){
            suml += event_l[pl][1];
            cntl += sgn(event_l[pl][1]);
            pl++;
        }
        while(pr < (int)event_r.size() && event_r[pr][0] <= x){
            sumr += event_r[pr][1];
            cntr += sgn(event_r[pr][1]);
            pr++;
        }
        cout << suml - cntl*x + cntr*x - sumr << "\n";
    }
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
}

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