Submission #1127538

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127538		lam	Reconstruction Project (JOI22_reconstruction)	C++20	7 / 100	5094 ms	14024 KiB

reconstruction

#include <bits/stdc++.h>

using namespace std;

#define int long long

vector<array<int, 3>> edge;
int x;
bool cmp(array<int, 3> a, array<int, 3> b){
    return abs(x - a[0]) < abs(x - b[0]);
}

struct DSU{
    vector<int> p;

    void init(int n){
        p.assign(n + 2, 0);
        for(int i = 1; i <= n; i++) p[i] = i;
    }

    int find(int u){
        if(p[u] == u) return u;
        else return p[u] = find(p[u]);
    }

    bool merge(int u, int v){
        u = find(u);
        v = find(v);
        if(u == v) return false;
        else{
            p[u] = v;
            return true;
        }
    }
} dsu;
void solve(){
   int n, m; cin >> n >> m;

    bool sub3 = true;

   for(int i = 1; i <= m; i++){
        int a, b, w; cin >> a >> b >> w;
        edge.push_back({w, b, a});
        if(b != a + 1) sub3 = false;
   }

    if(sub3){
        vector<vector<int>> v(n, vector<int>(0));
        for(int i = 0; i < m; i++) v[edge[i][2]].push_back(edge[i][0]);
        for(int i = 1; i <= n - 1; i++) sort(v[i].begin(), v[i].end());

        int q; cin >> q;

        while(q--){
            cin >> x;

            int ans = 0;
            for(int i = 1; i <= n - 1; i++){
                int c = 2e9;
                int pos = lower_bound(v[i].begin(), v[i].end(), x) - v[i].begin();
                if(pos < v[i].size()) c = min(c, v[i][pos] - x);
                if(pos != 0) c = min(c, x - v[i][pos - 1]);
                ans += c;
            }

            cout << ans << "\n";

        }
        return;

    }
   int q; cin >> q;

   while(q--){
        cin >> x;
        sort(edge.begin(), edge.end(), cmp);
        dsu.init(n);

        int ans = 0;
        for(int i = 0; i < m; i++){
            int u = edge[i][1], v = edge[i][2];
            if(dsu.merge(u, v)){
                ans += abs(x - edge[i][0]);
            }
        }

        cout << ans << "\n";
   }
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    // freopen("RAILROAD.INP", "r", stdin);
    // freopen("RAILROAD.OUT", "w", stdout);

    solve();
}

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