oj.uz

Submission #1000360

# Submission time Handle Problem Language Result Execution time Memory
1000360 2024-06-17T10:20:48 Z 79brue Reconstruction Project (JOI22_reconstruction) C++17
42 / 100
 404 ms 116252 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[100002];
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 3420 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 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 3672 KB Output is correct
7 Correct 1 ms 2652 KB Output is correct
8 Correct 1 ms 3420 KB Output is correct
9 Correct 1 ms 2652 KB Output is correct
10 Correct 1 ms 2652 KB Output is correct
11 Correct 1 ms 2648 KB Output is correct
12 Correct 1 ms 3416 KB Output is correct
13 Correct 1 ms 3420 KB Output is correct
14 Correct 2 ms 2652 KB Output is correct
15 Correct 2 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 3420 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 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 3672 KB Output is correct
7 Correct 1 ms 2652 KB Output is correct
8 Correct 1 ms 3420 KB Output is correct
9 Correct 1 ms 2652 KB Output is correct
10 Correct 1 ms 2652 KB Output is correct
11 Correct 1 ms 2648 KB Output is correct
12 Correct 1 ms 3416 KB Output is correct
13 Correct 1 ms 3420 KB Output is correct
14 Correct 2 ms 2652 KB Output is correct
15 Correct 2 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 271 ms 7604 KB Output is correct
21 Correct 332 ms 7760 KB Output is correct
22 Correct 284 ms 7692 KB Output is correct
23 Correct 272 ms 7764 KB Output is correct
24 Correct 237 ms 9812 KB Output is correct
25 Correct 256 ms 8276 KB Output is correct
26 Correct 271 ms 7768 KB Output is correct
27 Correct 268 ms 8284 KB Output is correct
28 Correct 268 ms 8532 KB Output is correct
29 Correct 267 ms 8312 KB Output is correct
30 Correct 271 ms 8284 KB Output is correct
31 Correct 274 ms 8532 KB Output is correct
32 Correct 273 ms 8276 KB Output is correct
33 Correct 280 ms 7764 KB Output is correct
34 Correct 269 ms 7768 KB Output is correct
35 Correct 266 ms 8280 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 2 ms 2652 KB Output is correct
4 Runtime error 404 ms 116252 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3420 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 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 3672 KB Output is correct
7 Correct 1 ms 2652 KB Output is correct
8 Correct 1 ms 3420 KB Output is correct
9 Correct 1 ms 2652 KB Output is correct
10 Correct 1 ms 2652 KB Output is correct
11 Correct 1 ms 2648 KB Output is correct
12 Correct 1 ms 3416 KB Output is correct
13 Correct 1 ms 3420 KB Output is correct
14 Correct 2 ms 2652 KB Output is correct
15 Correct 2 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 Runtime error 195 ms 109324 KB Execution killed with signal 11
21 Halted 0 ms 0 KB -

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3420 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 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 3672 KB Output is correct
7 Correct 1 ms 2652 KB Output is correct
8 Correct 1 ms 3420 KB Output is correct
9 Correct 1 ms 2652 KB Output is correct
10 Correct 1 ms 2652 KB Output is correct
11 Correct 1 ms 2648 KB Output is correct
12 Correct 1 ms 3416 KB Output is correct
13 Correct 1 ms 3420 KB Output is correct
14 Correct 2 ms 2652 KB Output is correct
15 Correct 2 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 271 ms 7604 KB Output is correct
21 Correct 332 ms 7760 KB Output is correct
22 Correct 284 ms 7692 KB Output is correct
23 Correct 272 ms 7764 KB Output is correct
24 Correct 237 ms 9812 KB Output is correct
25 Correct 256 ms 8276 KB Output is correct
26 Correct 271 ms 7768 KB Output is correct
27 Correct 268 ms 8284 KB Output is correct
28 Correct 268 ms 8532 KB Output is correct
29 Correct 267 ms 8312 KB Output is correct
30 Correct 271 ms 8284 KB Output is correct
31 Correct 274 ms 8532 KB Output is correct
32 Correct 273 ms 8276 KB Output is correct
33 Correct 280 ms 7764 KB Output is correct
34 Correct 269 ms 7768 KB Output is correct
35 Correct 266 ms 8280 KB Output is correct
36 Correct 280 ms 9120 KB Output is correct
37 Correct 319 ms 9112 KB Output is correct
38 Correct 299 ms 9040 KB Output is correct
39 Correct 312 ms 9132 KB Output is correct
40 Correct 248 ms 9680 KB Output is correct
41 Correct 268 ms 9044 KB Output is correct
42 Correct 283 ms 9040 KB Output is correct
43 Correct 280 ms 9040 KB Output is correct
44 Correct 276 ms 9556 KB Output is correct
45 Correct 270 ms 9552 KB Output is correct
46 Correct 282 ms 8956 KB Output is correct
47 Correct 291 ms 9124 KB Output is correct
48 Correct 319 ms 9040 KB Output is correct
49 Correct 307 ms 9096 KB Output is correct
50 Correct 272 ms 9852 KB Output is correct
51 Correct 282 ms 9040 KB Output is correct

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3420 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 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 3672 KB Output is correct
7 Correct 1 ms 2652 KB Output is correct
8 Correct 1 ms 3420 KB Output is correct
9 Correct 1 ms 2652 KB Output is correct
10 Correct 1 ms 2652 KB Output is correct
11 Correct 1 ms 2648 KB Output is correct
12 Correct 1 ms 3416 KB Output is correct
13 Correct 1 ms 3420 KB Output is correct
14 Correct 2 ms 2652 KB Output is correct
15 Correct 2 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 271 ms 7604 KB Output is correct
21 Correct 332 ms 7760 KB Output is correct
22 Correct 284 ms 7692 KB Output is correct
23 Correct 272 ms 7764 KB Output is correct
24 Correct 237 ms 9812 KB Output is correct
25 Correct 256 ms 8276 KB Output is correct
26 Correct 271 ms 7768 KB Output is correct
27 Correct 268 ms 8284 KB Output is correct
28 Correct 268 ms 8532 KB Output is correct
29 Correct 267 ms 8312 KB Output is correct
30 Correct 271 ms 8284 KB Output is correct
31 Correct 274 ms 8532 KB Output is correct
32 Correct 273 ms 8276 KB Output is correct
33 Correct 280 ms 7764 KB Output is correct
34 Correct 269 ms 7768 KB Output is correct
35 Correct 266 ms 8280 KB Output is correct
36 Correct 1 ms 2652 KB Output is correct
37 Correct 1 ms 2652 KB Output is correct
38 Correct 2 ms 2652 KB Output is correct
39 Runtime error 404 ms 116252 KB Execution killed with signal 11
40 Halted 0 ms 0 KB -