Submission #751003

#	Time	Username	Problem	Language	Result	Execution time	Memory
751003		puppy	Reconstruction Project (JOI22_reconstruction)	C++17	31 / 100	3708 ms	34796 KiB

reconstruction

#include <iostream>
#include <vector>
#include <algorithm>
#define int long long
using namespace std;

int N;
int M;
pair<pair<int, int>, int> edge[1005];
bool use[1005];

struct UnionFind
{
    vector<int> par;
    UnionFind(int n){par.resize(n+1); for(int i=1;i<=n;i++) par[i] = i;}
    void init(int n){par.resize(n+1); for(int i=1;i<=n;i++) par[i] = i;}
    int fin(int i){return i==par[i]?i:(par[i] = fin(par[i]));}
    void uni(int u, int v){par[fin(u)] = fin(v);}
    bool isuni(int u, int v){return fin(u) == fin(v);}
};
signed main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> N >> M;
    for (int i = 0; i < M; i++) {
        cin >> edge[i].first.first >> edge[i].first.second >> edge[i].second;
    }
    sort(edge, edge + M, [&](auto &i, auto &j){return i.second < j.second;});
    UnionFind uf(N);
    for (int i = 0; i < M; i++) {
        if (!uf.isuni(edge[i].first.first, edge[i].first.second)) {
            uf.uni(edge[i].first.first, edge[i].first.second);
            use[i] = true;
        }
    }
    vector<pair<int, pair<int, int>>> vc;
    for (int i = 0; i < M; i++) {
        for (int j = i + 1; j < M; j++) {
            int p = edge[i].second, q = edge[j].second;
            vc.push_back(make_pair((p+q+1)/2, make_pair(i, j)));
        }
    }
    int pv = 0;
    sort(vc.begin(), vc.end());
    int Q; cin >> Q;
    while (Q--) {
        int a; cin >> a;
        while (pv < (int)vc.size() && vc[pv].first <= a) {
            int fi = vc[pv].second.first, se = vc[pv].second.second;
            if (use[fi]) {
                uf.init(N);
                for (int i = 0; i < M; i++) {
                    if (i != fi && use[i]) uf.uni(edge[i].first.first, edge[i].first.second);
                }
                if (!uf.isuni(edge[se].first.first, edge[se].first.second)) {
                    use[fi] = false;
                    use[se] = true;
                }
            }
            pv++;
        }
        int ans = 0;
        for (int i = 0; i < M; i++) {
            if (use[i]) {
                ans += abs(a - edge[i].second);
            }
        }
        cout << ans << '\n';
    }
}

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