Submission #999804

#	Time	Username	Problem	Language	Result	Execution time	Memory
999804		79brue	Reconstruction Project (JOI22_reconstruction)	C++17	7 / 100	5086 ms	24660 KiB

reconstruction

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

void input();
void solve();

int main(){
    input();
    solve();
}

struct Edge{
    int a, b; ll w;
    Edge(){}
    Edge(int a, int b, ll w): a(a), b(b), w(w){}
    bool operator<(const Edge &r)const{
        return w<r.w;
    }
};

int n, m, q;
Edge edge[100002];
ll queries[1000002];

void input(){
    scanf("%d %d", &n, &m);
    for(int i=1; i<=m; i++) scanf("%d %d %lld", &edge[i].a, &edge[i].b, &edge[i].w);
    sort(edge+1, edge+m+1);
    scanf("%d", &q);
    for(int i=1; i<=q; i++) scanf("%lld", &queries[i]);
}

struct unionFind{
    int par[100002];

    void init(int n){
        for(int i=1; i<=n; i++) par[i] = i;
    }

    int find(int x){
        if(x == par[x]) return x;
        return par[x] = find(par[x]);
    }

    void merge(int x, int y){
        x = find(x), y = find(y);
        par[y] = x;
    }
} dsu;

bool used[100002], visited[100002];
vector<int> link[100002];
ll ans[100002];

int getMin(int x, int p, int y, int minV = INT_MAX){
    if(x == y) return minV;
    for(int nxt: link[x]){
        int nxtV = edge[nxt].a ^ edge[nxt].b ^ x;
        if(nxtV == p) continue;
        int tmp = getMin(nxtV, x, y, min(minV, nxt));
        if(tmp != -1) return tmp;
    }
    return -1;
}

void solve(){
    /// get first mst
    dsu.init(n);
    for(int i=1; i<=m; i++){
        if(dsu.find(edge[i].a) == dsu.find(edge[i].b)) continue;
        dsu.merge(edge[i].a, edge[i].b);
        link[edge[i].a].push_back(i);
        link[edge[i].b].push_back(i);
        used[i] = 1;
    }

    for(int tq=1; tq<=q; tq++){
        ll W = queries[tq];
        for(int i=1; i<=m; i++){
            if(used[i]) continue;
            int tmp = getMin(edge[i].a, -1, edge[i].b);
            assert(tmp != -1);
            if(abs(W - edge[tmp].w) > abs(W - edge[i].w)){
                used[tmp] = 0, used[i] = 1;
                link[edge[tmp].a].erase(find(link[edge[tmp].a].begin(), link[edge[tmp].a].end(), tmp));
                link[edge[tmp].b].erase(find(link[edge[tmp].b].begin(), link[edge[tmp].b].end(), tmp));
                link[edge[i].a].push_back(i);
                link[edge[i].b].push_back(i);
            }
        }

        ll sum = 0;
        for(int i=1; i<=m; i++) if(used[i]) sum += abs(W - edge[i].w);
        printf("%lld\n", sum);
    }
}

Compilation message (stderr)

reconstruction.cpp: In function 'void input()':
reconstruction.cpp:29:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
reconstruction.cpp:30:34: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |     for(int i=1; i<=m; i++) scanf("%d %d %lld", &edge[i].a, &edge[i].b, &edge[i].w);
      |                             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
reconstruction.cpp:32:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |     scanf("%d", &q);
      |     ~~~~~^~~~~~~~~~
reconstruction.cpp:33:34: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |     for(int i=1; i<=q; i++) scanf("%lld", &queries[i]);
      |                             ~~~~~^~~~~~~~~~~~~~~~~~~~~

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