Submission #1127536

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127536		lam	Reconstruction Project (JOI22_reconstruction)	C++20	14 / 100	1333 ms	19460 KiB

reconstruction

#include <iostream>
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll INF = 4e18;
struct edge{
    ll u, v, w;
};
struct DSU{
    vector<int> pa;
    vector<int> sz;
    int n;
    DSU(int n) : n(n){
        pa.resize(n+1);
        sz.resize(n+1, 1);
        iota(pa.begin(), pa.end(), 0);
    }
    int find(int v){
        if(v == pa[v]) return v;
        int res = find(pa[v]);
        pa[v] = res;
        return res;
    }
    void merge(int u, int v){
        u = find(u); v = find(v);
        if(sz[u] < sz[v]) swap(u, v);
        pa[v] = u;
        sz[u] += sz[v];
    }
};
void sub2(int n, int m, int Q, vector<edge> e){
    for(int it = 1; it <= Q; it++){
        ll x;
        cin >> x;
        vector<edge> ed = e;
        for(int i = 0; i < m; i++){
            ed[i].w = abs(x-e[i].w);
        }
        sort(ed.begin(), ed.end(), [&](edge a, edge b){return a.w < b.w;});
        ll ans = 0;
        DSU dsu(n+1);
        for(auto it : ed){
            ll u = it.u, v = it.v, w = it.w;
            if(dsu.find(u) == dsu.find(v)) continue;
            dsu.merge(u, v);
            ans += w;
        }
        cout << ans << "\n";
    }
}
void sub3(int n, int m, int Q, vector<edge> e){
    vector<vector<ll>> s(n+1);
    for(auto it : e){
        s[it.u].push_back(it.w);
    }
    for(int i = 1; i < n; i++){
        sort(s[i].begin(), s[i].end());
    }
    vector<int> pt(n+1, 0);
    for(int it = 1; it <= Q; it++){
        ll x;
        cin >> x;
        ll ans = 0;
        for(int i = 1; i < n; i++){
            while(pt[i] < (int)s[i].size() && s[i][pt[i]] < x){
                pt[i]++;
            }
            ll mn = INF;
            if(pt[i] < (int)s[i].size()){
                mn = s[i][pt[i]]-x;
            }
            if(pt[i]-1 >= 0){
                mn = min(mn, x-s[i][pt[i]-1]);
            }
            ans += mn;
        }
        cout << ans << "\n";
    }
}
void solve(){
    int n, m, Q;
    cin >> n >> m;
    vector<edge> e(m);
    bool issub3 = true;
    for(int i = 1; i <= m; i++){
        ll u, v, w;
        cin >> u >> v >> w;
        if(v != u+1) issub3 = false;
        e[i-1] = {u, v, w};
    }
    cin >> Q;
    if(Q <= 10){
        sub2(n, m, Q, e);
        return;
    }
    if(issub3){
        sub3(n, m, Q, e);
        return;
    }
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    // freopen("RAILROAD.inp", "r", stdin);
    // freopen("RAILROAD.out", "w", stdout);
    solve();
    return 0;
}

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