oj.uz

Submission #1000362

# Submission time Handle Problem Language Result Execution time Memory
1000362 2024-06-17T10:21:32 Z 79brue Reconstruction Project (JOI22_reconstruction) C++17
100 / 100
 637 ms 77408 KB 
#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

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.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 2812 KB Output is correct
3 Correct 2 ms 2652 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 1 ms 2652 KB Output is correct
7 Correct 1 ms 2652 KB Output is correct
8 Correct 1 ms 2740 KB Output is correct
9 Correct 1 ms 2652 KB Output is correct
10 Correct 2 ms 2652 KB Output is correct
11 Correct 1 ms 2652 KB Output is correct
12 Correct 1 ms 2652 KB Output is correct
13 Correct 2 ms 2652 KB Output is correct
14 Correct 1 ms 2652 KB Output is correct
15 Correct 1 ms 2652 KB Output is correct
16 Correct 1 ms 2652 KB Output is correct
17 Correct 1 ms 2652 KB Output is correct
18 Correct 1 ms 2652 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 2812 KB Output is correct
3 Correct 2 ms 2652 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 1 ms 2652 KB Output is correct
7 Correct 1 ms 2652 KB Output is correct
8 Correct 1 ms 2740 KB Output is correct
9 Correct 1 ms 2652 KB Output is correct
10 Correct 2 ms 2652 KB Output is correct
11 Correct 1 ms 2652 KB Output is correct
12 Correct 1 ms 2652 KB Output is correct
13 Correct 2 ms 2652 KB Output is correct
14 Correct 1 ms 2652 KB Output is correct
15 Correct 1 ms 2652 KB Output is correct
16 Correct 1 ms 2652 KB Output is correct
17 Correct 1 ms 2652 KB Output is correct
18 Correct 1 ms 2652 KB Output is correct
19 Correct 1 ms 2652 KB Output is correct
20 Correct 268 ms 5892 KB Output is correct
21 Correct 322 ms 6228 KB Output is correct
22 Correct 285 ms 8028 KB Output is correct
23 Correct 307 ms 7416 KB Output is correct
24 Correct 233 ms 5984 KB Output is correct
25 Correct 258 ms 5972 KB Output is correct
26 Correct 300 ms 5964 KB Output is correct
27 Correct 268 ms 5976 KB Output is correct
28 Correct 265 ms 6080 KB Output is correct
29 Correct 271 ms 5960 KB Output is correct
30 Correct 277 ms 5968 KB Output is correct
31 Correct 272 ms 6228 KB Output is correct
32 Correct 267 ms 5980 KB Output is correct
33 Correct 275 ms 5976 KB Output is correct
34 Correct 332 ms 8052 KB Output is correct
35 Correct 268 ms 7520 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4184 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 372 ms 63948 KB Output is correct
5 Correct 381 ms 75392 KB Output is correct
6 Correct 372 ms 75348 KB Output is correct
7 Correct 572 ms 77140 KB Output is correct
8 Correct 637 ms 77396 KB Output is correct
9 Correct 516 ms 77408 KB Output is correct
10 Correct 364 ms 75508 KB Output is correct
11 Correct 561 ms 77380 KB Output is correct

Subtask #4
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 2812 KB Output is correct
3 Correct 2 ms 2652 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 1 ms 2652 KB Output is correct
7 Correct 1 ms 2652 KB Output is correct
8 Correct 1 ms 2740 KB Output is correct
9 Correct 1 ms 2652 KB Output is correct
10 Correct 2 ms 2652 KB Output is correct
11 Correct 1 ms 2652 KB Output is correct
12 Correct 1 ms 2652 KB Output is correct
13 Correct 2 ms 2652 KB Output is correct
14 Correct 1 ms 2652 KB Output is correct
15 Correct 1 ms 2652 KB Output is correct
16 Correct 1 ms 2652 KB Output is correct
17 Correct 1 ms 2652 KB Output is correct
18 Correct 1 ms 2652 KB Output is correct
19 Correct 1 ms 4184 KB Output is correct
20 Correct 220 ms 61912 KB Output is correct
21 Correct 215 ms 71764 KB Output is correct
22 Correct 166 ms 71672 KB Output is correct
23 Correct 167 ms 71764 KB Output is correct
24 Correct 211 ms 71540 KB Output is correct
25 Correct 204 ms 71764 KB Output is correct
26 Correct 163 ms 71760 KB Output is correct
27 Correct 202 ms 71612 KB Output is correct
28 Correct 183 ms 71764 KB Output is correct
29 Correct 174 ms 71764 KB Output is correct
30 Correct 174 ms 71836 KB Output is correct
31 Correct 169 ms 71624 KB Output is correct
32 Correct 170 ms 72280 KB Output is correct
33 Correct 183 ms 71612 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 2812 KB Output is correct
3 Correct 2 ms 2652 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 1 ms 2652 KB Output is correct
7 Correct 1 ms 2652 KB Output is correct
8 Correct 1 ms 2740 KB Output is correct
9 Correct 1 ms 2652 KB Output is correct
10 Correct 2 ms 2652 KB Output is correct
11 Correct 1 ms 2652 KB Output is correct
12 Correct 1 ms 2652 KB Output is correct
13 Correct 2 ms 2652 KB Output is correct
14 Correct 1 ms 2652 KB Output is correct
15 Correct 1 ms 2652 KB Output is correct
16 Correct 1 ms 2652 KB Output is correct
17 Correct 1 ms 2652 KB Output is correct
18 Correct 1 ms 2652 KB Output is correct
19 Correct 1 ms 2652 KB Output is correct
20 Correct 268 ms 5892 KB Output is correct
21 Correct 322 ms 6228 KB Output is correct
22 Correct 285 ms 8028 KB Output is correct
23 Correct 307 ms 7416 KB Output is correct
24 Correct 233 ms 5984 KB Output is correct
25 Correct 258 ms 5972 KB Output is correct
26 Correct 300 ms 5964 KB Output is correct
27 Correct 268 ms 5976 KB Output is correct
28 Correct 265 ms 6080 KB Output is correct
29 Correct 271 ms 5960 KB Output is correct
30 Correct 277 ms 5968 KB Output is correct
31 Correct 272 ms 6228 KB Output is correct
32 Correct 267 ms 5980 KB Output is correct
33 Correct 275 ms 5976 KB Output is correct
34 Correct 332 ms 8052 KB Output is correct
35 Correct 268 ms 7520 KB Output is correct
36 Correct 303 ms 8408 KB Output is correct
37 Correct 319 ms 8488 KB Output is correct
38 Correct 340 ms 8528 KB Output is correct
39 Correct 284 ms 8276 KB Output is correct
40 Correct 253 ms 8272 KB Output is correct
41 Correct 274 ms 8276 KB Output is correct
42 Correct 282 ms 8384 KB Output is correct
43 Correct 315 ms 8404 KB Output is correct
44 Correct 300 ms 8432 KB Output is correct
45 Correct 273 ms 8284 KB Output is correct
46 Correct 282 ms 8276 KB Output is correct
47 Correct 310 ms 8276 KB Output is correct
48 Correct 317 ms 8460 KB Output is correct
49 Correct 280 ms 8272 KB Output is correct
50 Correct 301 ms 8532 KB Output is correct
51 Correct 283 ms 8448 KB Output is correct

Subtask #6
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 2812 KB Output is correct
3 Correct 2 ms 2652 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 1 ms 2652 KB Output is correct
7 Correct 1 ms 2652 KB Output is correct
8 Correct 1 ms 2740 KB Output is correct
9 Correct 1 ms 2652 KB Output is correct
10 Correct 2 ms 2652 KB Output is correct
11 Correct 1 ms 2652 KB Output is correct
12 Correct 1 ms 2652 KB Output is correct
13 Correct 2 ms 2652 KB Output is correct
14 Correct 1 ms 2652 KB Output is correct
15 Correct 1 ms 2652 KB Output is correct
16 Correct 1 ms 2652 KB Output is correct
17 Correct 1 ms 2652 KB Output is correct
18 Correct 1 ms 2652 KB Output is correct
19 Correct 1 ms 2652 KB Output is correct
20 Correct 268 ms 5892 KB Output is correct
21 Correct 322 ms 6228 KB Output is correct
22 Correct 285 ms 8028 KB Output is correct
23 Correct 307 ms 7416 KB Output is correct
24 Correct 233 ms 5984 KB Output is correct
25 Correct 258 ms 5972 KB Output is correct
26 Correct 300 ms 5964 KB Output is correct
27 Correct 268 ms 5976 KB Output is correct
28 Correct 265 ms 6080 KB Output is correct
29 Correct 271 ms 5960 KB Output is correct
30 Correct 277 ms 5968 KB Output is correct
31 Correct 272 ms 6228 KB Output is correct
32 Correct 267 ms 5980 KB Output is correct
33 Correct 275 ms 5976 KB Output is correct
34 Correct 332 ms 8052 KB Output is correct
35 Correct 268 ms 7520 KB Output is correct
36 Correct 1 ms 4184 KB Output is correct
37 Correct 1 ms 2652 KB Output is correct
38 Correct 1 ms 2652 KB Output is correct
39 Correct 372 ms 63948 KB Output is correct
40 Correct 381 ms 75392 KB Output is correct
41 Correct 372 ms 75348 KB Output is correct
42 Correct 572 ms 77140 KB Output is correct
43 Correct 637 ms 77396 KB Output is correct
44 Correct 516 ms 77408 KB Output is correct
45 Correct 364 ms 75508 KB Output is correct
46 Correct 561 ms 77380 KB Output is correct
47 Correct 1 ms 4184 KB Output is correct
48 Correct 220 ms 61912 KB Output is correct
49 Correct 215 ms 71764 KB Output is correct
50 Correct 166 ms 71672 KB Output is correct
51 Correct 167 ms 71764 KB Output is correct
52 Correct 211 ms 71540 KB Output is correct
53 Correct 204 ms 71764 KB Output is correct
54 Correct 163 ms 71760 KB Output is correct
55 Correct 202 ms 71612 KB Output is correct
56 Correct 183 ms 71764 KB Output is correct
57 Correct 174 ms 71764 KB Output is correct
58 Correct 174 ms 71836 KB Output is correct
59 Correct 169 ms 71624 KB Output is correct
60 Correct 170 ms 72280 KB Output is correct
61 Correct 183 ms 71612 KB Output is correct
62 Correct 303 ms 8408 KB Output is correct
63 Correct 319 ms 8488 KB Output is correct
64 Correct 340 ms 8528 KB Output is correct
65 Correct 284 ms 8276 KB Output is correct
66 Correct 253 ms 8272 KB Output is correct
67 Correct 274 ms 8276 KB Output is correct
68 Correct 282 ms 8384 KB Output is correct
69 Correct 315 ms 8404 KB Output is correct
70 Correct 300 ms 8432 KB Output is correct
71 Correct 273 ms 8284 KB Output is correct
72 Correct 282 ms 8276 KB Output is correct
73 Correct 310 ms 8276 KB Output is correct
74 Correct 317 ms 8460 KB Output is correct
75 Correct 280 ms 8272 KB Output is correct
76 Correct 301 ms 8532 KB Output is correct
77 Correct 283 ms 8448 KB Output is correct
78 Correct 506 ms 74256 KB Output is correct
79 Correct 488 ms 76292 KB Output is correct
80 Correct 485 ms 75524 KB Output is correct
81 Correct 463 ms 75260 KB Output is correct
82 Correct 412 ms 74520 KB Output is correct
83 Correct 434 ms 74332 KB Output is correct
84 Correct 443 ms 74324 KB Output is correct
85 Correct 488 ms 74388 KB Output is correct
86 Correct 480 ms 74416 KB Output is correct
87 Correct 469 ms 76012 KB Output is correct
88 Correct 499 ms 74392 KB Output is correct
89 Correct 449 ms 74324 KB Output is correct
90 Correct 479 ms 74524 KB Output is correct
91 Correct 479 ms 74340 KB Output is correct
92 Correct 495 ms 77140 KB Output is correct
93 Correct 470 ms 75592 KB Output is correct