제출 #1127534

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1127534		lam	Reconstruction Project (JOI22_reconstruction)	C++20	7 / 100	5092 ms	12972 KiB

reconstruction

#include <bits/stdc++.h>
#define int long long
#define pii pair<int, int>

using namespace std;

const int N = 502, M = 1e5 + 5, Q = 1e6 + 5, LOG = 20;

int n, m, q, a[M], b[M], w[M], x[Q];

struct edge{
    int u, v, w;
};

struct DSU{
    int n; vector<int> par, sz;

    void init(int _n){
        n = _n;
        par.resize(n + 1, 0), sz.resize(n + 1, 0);
        for(int i = 0; i <= n; i++) par[i] = i, sz[i] = 1;
     }

     int root(int x){
        return par[x] = (x == par[x] ? x : root(par[x]));
     }

     void unite(int x, int y){
        x = root(x), y = root(y); if(x == y) return;
        if(sz[x] < sz[y]) swap(x, y);
        sz[x] += sz[y], par[y] = x;
     }
};

namespace brute{
    edge e[M]; DSU ds;
    void solve(){
        ds.init(n);
        for(int i = 1; i <= q; i++){
            for(int j = 1; j <= n; j++) ds.par[j] = j, ds.sz[j] = 1;
            for(int j = 1; j <= m; j++){
                e[j].u = a[j], e[j].v = b[j], e[j].w = abs(x[i] - w[j]);
            }
            sort(e + 1, e + m + 1, [](edge x, edge y){return x.w < y.w;});
            int cost = 0;
            for(int j = 1; j <= m; j++){
                if(ds.root(e[j].u) != ds.root(e[j].v)) cost += e[j].w;
                ds.unite(e[j].u, e[j].v);
            }
            cout << cost << '\n';
        }
    }
}

namespace line{
    void solve(){
        vector<int> v, ps(m);
        for(int i = 1; i <= m; i++){
            v.push_back(w[i]);
        }
        sort(v.begin(), v.end());
        for(int i = 0; i < m; i++){
            ps[i] = (i ? ps[i - 1] : 0) + v[i];
        }
        for(int i = 1; i <= q; i++){
            int id = lower_bound(v.begin(), v.end(), x[i]) - v.begin() - 1;
            int ans = (ps.back() - (id >= 0 ? ps[id] : 0)) - x[i] * (ps.size() - id - 1);
            if(id >= 0) ans += x[i] * (id + 1) - ps[id];
            cout << ans << '\n';
        }
    }
}

//namespace idk{
//    edge e[M];
//    DSU MST; vector<pii> adj[N];
//    int h[N], par[20][N], ans[Q];
//    set<pii> s[N];
//    void dfs(int i, int pre){
//        for(int x : adj[i]){
//            if(x == pre) continue;
//            dfs(x, i);
//            if(s[x].size() > s[i].size()) swap(s[x], s[i]);
//            for(pii y : s[x]){
//                if(s[i].find(y) != s[i].end()) s[i].erase(y);
//                else s[i].insert(y);
//            }
//        }
//        for(pii x : s[i]){
//            int w = x.first;
//            int lo = 1, hi = q, pos = q + 1;
//            while(lo <= hi){
//                int mid = (lo + hi) / 2;
//                if(x[mid] >= w){
//                    hi = mid - 1, pos = mid;
//                } else{
//                    lo = mid + 1;
//                }
//            }
//
//            lo =
//        }
//    }
//
//    void solve(){
//        MST.init(n);
//        for(int i = 1; i <= m; i++){
//            e[i] = {a[i], b[i], w[i]};
//        }
//        sort(e + 1, e + m + 1, [](edge x, edge y){return x.w < y.w})
//        int cost = 0;
//        for(int j = 1; j <= m; j++){
//            if(ds.root(e[j].u) != ds.root(e[j].v)) cost += e[j].w;
//            ds.unite(e[j].u, e[j].v);
//            adj[e[j].u].push_back({e[j].v, e[j].w}), adj[e[j].v].push_back({e[j].u, e[j].w});
//            cost += e[j].w;
//        }
//        ans[0] = cost;
//        for(int i = 1; i <= n; i++)
//        for(int i = 1; i <= m; i++){
//            s[a[i]].insert({w[i], i});
//            s[b[i]].insert({w[i], i});
//        }
//        dfs(1, 1);
//    }
//}
signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

    #define task "RAILROAD"
    // if(fopen(task ".inp", "r")){
    //     freopen(task ".inp", "r", stdin);
    //     freopen(task ".out", "w", stdout);
    // }
    cin >> n >> m;
    for(int i = 1; i <= m; i++) cin >> a[i] >> b[i] >> w[i];
    cin >> q;
    for(int i = 1; i <= q; i++) cin >> x[i];

    if(m == n - 1)
        return line::solve(), 0;

    return brute::solve(), 0;
//    idk::solve();
}


/*

5 10
1 2 8
1 3 13
1 4 5
1 5 11
1 5 3
2 3 7
2 4 15
3 4 6
3 5 6
4 5 2
6
3
6
8
10
13
17

3 4
1 2 1
1 2 4
2 3 2
2 3 4
4
1
2
3
4


4 3
1 2 1
2 3 4
3 4 5
5
1 2 3 4 5
*/

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