Submission #1000362

#	Time	Username	Problem	Language	Result	Execution time	Memory
1000362		79brue	Reconstruction Project (JOI22_reconstruction)	C++17	100 / 100	637 ms	77408 KiB

reconstruction

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const ll INF = 1e18;

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[1000002];
ll L[100002], R[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;
}

ll down[1000002], downSum[1000002];
ll up[1000002], upSum[1000002];

void solve(){
    for(int i=1; i<=m; i++) L[i] = INF, R[i] = -INF;

    /// 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;
        L[i] = 0;
    }

    for(int i=1; i<=m; i++){
        if(used[i]) continue;
        int pnt = getMin(edge[i].a, -1, edge[i].b);
        used[pnt] = 0, used[i] = 1;
        link[edge[pnt].a].erase(find(link[edge[pnt].a].begin(), link[edge[pnt].a].end(), pnt));
        link[edge[pnt].b].erase(find(link[edge[pnt].b].begin(), link[edge[pnt].b].end(), pnt));
        link[edge[i].a].push_back(i);
        link[edge[i].b].push_back(i);

        ll v = (edge[i].w + edge[pnt].w);
        R[pnt] = v / 2;
        L[i] = v / 2 + 1;
    }
    for(int i=1; i<=m; i++) if(L[i] != INF && R[i] == -INF) R[i] = INF;

    for(int i=1; i<=m; i++){
        if(L[i] == INF) continue;
        int l = lower_bound(queries+1, queries+q+1, L[i]) - queries;
        int m = lower_bound(queries+1, queries+q+1, edge[i].w) - queries;
        int r = upper_bound(queries+1, queries+q+1, R[i]) - queries;

        down[l]++, downSum[l] += edge[i].w;
        down[m]--, downSum[m] -= edge[i].w;
        up[m]++, upSum[m] += edge[i].w;
        up[r]--, upSum[r] -= edge[i].w;
    }

    for(int i=1; i<=q; i++){
        down[i] += down[i-1], downSum[i] += downSum[i-1];
        up[i] += up[i-1], upSum[i] += upSum[i-1];

        ans[i] += downSum[i] - down[i] * queries[i];
        ans[i] += up[i] * queries[i] - upSum[i];
        printf("%lld\n", ans[i]);
    }
}

Compilation message (stderr)

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

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