oj.uz

Submission #886361

# Submission time Handle Problem Language Result Execution time Memory
886361 2023-12-12T00:50:45 Z dong_liu Reconstruction Project (JOI22_reconstruction) C++17
42 / 100
 5000 ms 415028 KB 
#include <bits/stdc++.h>
using namespace std;

#define ar array
#define sz(v) int(std::size(v))
using i64 = long long;
using pii = pair<int, int>;

bool mem_st;

const int N = 500, M = 1e5, Q = 1e6;

struct edge {
    int i, j, w;
    bool operator<(const edge e) const {
        return w < e.w;
    }
};

struct arr : ar<int, N-1> {
    int sz = 0;
    void pb(int x) { at(sz++) = x; }
    auto end() { return begin()+sz; }
};

int n, m, q;
edge e[M];
arr pf[M+1], sf[M+1];

struct {
    int p[N];
    void init() {
        for (int i = 0; i < n; i++) p[i] = i;
    }
    int find(int i) {
        return p[i] == i ? i : p[i] = find(p[i]);
    }
    bool join(int i, int j) {
        i = find(i), j = find(j);
        if (i == j) return false;
        p[i] = j;
        return true;
    }
} dsu;

bool mem_en;


int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;
    for (int h = 0; h < m; h++) {
        cin >> e[h].i >> e[h].j >> e[h].w;
        e[h].i--, e[h].j--;
    }
    sort(e, e+m);
    for (int t = 1; t <= m; t++) {
        auto ins = [&](int h) {
            if (dsu.join(e[h].i, e[h].j))
                pf[t].pb(h);
        };
        dsu.init();
        ins(t-1);
        for (int h : pf[t-1]) ins(h);
    }
    for (int t = m-1; t >= 0; t--) {
        auto ins = [&](int h) {
            if (dsu.join(e[h].i, e[h].j))
                sf[t].pb(h);
        };
        dsu.init();
        ins(t);
        for (int h : sf[t+1]) ins(h);
    }
    cin >> q;
    int t = 0;
    while (q--) {
        int x;
        cin >> x;
        while (t < m && e[t].w <= x) t++;
        dsu.init();
        int one = 0, two = 0; i64 cost = 0;
        auto ins = [&](int h) {
            if (dsu.join(e[h].i, e[h].j))
                cost += abs(e[h].w - x);
        };
        while (one < pf[t].sz && two < sf[t].sz)
            if (x-e[pf[t][one]].w < e[sf[t][two]].w-x) ins(pf[t][one++]);
            else ins(sf[t][two++]);
        while (one < pf[t].sz) ins(pf[t][one++]);
        while (two < sf[t].sz) ins(sf[t][two++]);
        cout << cost << '\n';
    }
#if 0
    cout << double(&mem_en - &mem_st) / (1 << 20) << '\n';
#endif
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 392548 KB Output is correct
2 Correct 39 ms 392432 KB Output is correct
3 Correct 38 ms 392456 KB Output is correct
4 Correct 40 ms 392420 KB Output is correct
5 Correct 37 ms 392544 KB Output is correct
6 Correct 37 ms 392544 KB Output is correct
7 Correct 37 ms 392488 KB Output is correct
8 Correct 39 ms 392528 KB Output is correct
9 Correct 39 ms 392528 KB Output is correct
10 Correct 37 ms 392540 KB Output is correct
11 Correct 38 ms 392532 KB Output is correct
12 Correct 38 ms 392532 KB Output is correct
13 Correct 37 ms 392320 KB Output is correct
14 Correct 42 ms 392540 KB Output is correct
15 Correct 39 ms 392460 KB Output is correct
16 Correct 37 ms 392420 KB Output is correct
17 Correct 37 ms 392456 KB Output is correct
18 Correct 37 ms 392528 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 392548 KB Output is correct
2 Correct 39 ms 392432 KB Output is correct
3 Correct 38 ms 392456 KB Output is correct
4 Correct 40 ms 392420 KB Output is correct
5 Correct 37 ms 392544 KB Output is correct
6 Correct 37 ms 392544 KB Output is correct
7 Correct 37 ms 392488 KB Output is correct
8 Correct 39 ms 392528 KB Output is correct
9 Correct 39 ms 392528 KB Output is correct
10 Correct 37 ms 392540 KB Output is correct
11 Correct 38 ms 392532 KB Output is correct
12 Correct 38 ms 392532 KB Output is correct
13 Correct 37 ms 392320 KB Output is correct
14 Correct 42 ms 392540 KB Output is correct
15 Correct 39 ms 392460 KB Output is correct
16 Correct 37 ms 392420 KB Output is correct
17 Correct 37 ms 392456 KB Output is correct
18 Correct 37 ms 392528 KB Output is correct
19 Correct 38 ms 392532 KB Output is correct
20 Correct 1092 ms 394716 KB Output is correct
21 Correct 538 ms 394712 KB Output is correct
22 Correct 579 ms 394704 KB Output is correct
23 Correct 613 ms 394580 KB Output is correct
24 Correct 798 ms 394716 KB Output is correct
25 Correct 1161 ms 394832 KB Output is correct
26 Correct 1064 ms 394712 KB Output is correct
27 Correct 1052 ms 394708 KB Output is correct
28 Correct 1065 ms 394712 KB Output is correct
29 Correct 1071 ms 394716 KB Output is correct
30 Correct 1050 ms 394836 KB Output is correct
31 Correct 1072 ms 394832 KB Output is correct
32 Correct 1072 ms 394832 KB Output is correct
33 Correct 1074 ms 394832 KB Output is correct
34 Correct 1058 ms 394820 KB Output is correct
35 Correct 1057 ms 394708 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 392532 KB Output is correct
2 Correct 38 ms 392740 KB Output is correct
3 Correct 38 ms 392492 KB Output is correct
4 Execution timed out 5041 ms 404168 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 392548 KB Output is correct
2 Correct 39 ms 392432 KB Output is correct
3 Correct 38 ms 392456 KB Output is correct
4 Correct 40 ms 392420 KB Output is correct
5 Correct 37 ms 392544 KB Output is correct
6 Correct 37 ms 392544 KB Output is correct
7 Correct 37 ms 392488 KB Output is correct
8 Correct 39 ms 392528 KB Output is correct
9 Correct 39 ms 392528 KB Output is correct
10 Correct 37 ms 392540 KB Output is correct
11 Correct 38 ms 392532 KB Output is correct
12 Correct 38 ms 392532 KB Output is correct
13 Correct 37 ms 392320 KB Output is correct
14 Correct 42 ms 392540 KB Output is correct
15 Correct 39 ms 392460 KB Output is correct
16 Correct 37 ms 392420 KB Output is correct
17 Correct 37 ms 392456 KB Output is correct
18 Correct 37 ms 392528 KB Output is correct
19 Correct 37 ms 392528 KB Output is correct
20 Correct 4961 ms 414252 KB Output is correct
21 Correct 4366 ms 414552 KB Output is correct
22 Correct 4879 ms 414312 KB Output is correct
23 Correct 4819 ms 414516 KB Output is correct
24 Correct 4995 ms 414428 KB Output is correct
25 Correct 4962 ms 415028 KB Output is correct
26 Correct 4720 ms 414460 KB Output is correct
27 Correct 4654 ms 414740 KB Output is correct
28 Execution timed out 5002 ms 414324 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 392548 KB Output is correct
2 Correct 39 ms 392432 KB Output is correct
3 Correct 38 ms 392456 KB Output is correct
4 Correct 40 ms 392420 KB Output is correct
5 Correct 37 ms 392544 KB Output is correct
6 Correct 37 ms 392544 KB Output is correct
7 Correct 37 ms 392488 KB Output is correct
8 Correct 39 ms 392528 KB Output is correct
9 Correct 39 ms 392528 KB Output is correct
10 Correct 37 ms 392540 KB Output is correct
11 Correct 38 ms 392532 KB Output is correct
12 Correct 38 ms 392532 KB Output is correct
13 Correct 37 ms 392320 KB Output is correct
14 Correct 42 ms 392540 KB Output is correct
15 Correct 39 ms 392460 KB Output is correct
16 Correct 37 ms 392420 KB Output is correct
17 Correct 37 ms 392456 KB Output is correct
18 Correct 37 ms 392528 KB Output is correct
19 Correct 38 ms 392532 KB Output is correct
20 Correct 1092 ms 394716 KB Output is correct
21 Correct 538 ms 394712 KB Output is correct
22 Correct 579 ms 394704 KB Output is correct
23 Correct 613 ms 394580 KB Output is correct
24 Correct 798 ms 394716 KB Output is correct
25 Correct 1161 ms 394832 KB Output is correct
26 Correct 1064 ms 394712 KB Output is correct
27 Correct 1052 ms 394708 KB Output is correct
28 Correct 1065 ms 394712 KB Output is correct
29 Correct 1071 ms 394716 KB Output is correct
30 Correct 1050 ms 394836 KB Output is correct
31 Correct 1072 ms 394832 KB Output is correct
32 Correct 1072 ms 394832 KB Output is correct
33 Correct 1074 ms 394832 KB Output is correct
34 Correct 1058 ms 394820 KB Output is correct
35 Correct 1057 ms 394708 KB Output is correct
36 Correct 1568 ms 395100 KB Output is correct
37 Correct 882 ms 394904 KB Output is correct
38 Correct 971 ms 395212 KB Output is correct
39 Correct 1058 ms 395092 KB Output is correct
40 Correct 1298 ms 395468 KB Output is correct
41 Correct 1702 ms 395156 KB Output is correct
42 Correct 1584 ms 395028 KB Output is correct
43 Correct 1584 ms 395072 KB Output is correct
44 Correct 1252 ms 394900 KB Output is correct
45 Correct 1163 ms 394924 KB Output is correct
46 Correct 1568 ms 394904 KB Output is correct
47 Correct 1566 ms 395220 KB Output is correct
48 Correct 1585 ms 395172 KB Output is correct
49 Correct 1549 ms 395156 KB Output is correct
50 Correct 1114 ms 395488 KB Output is correct
51 Correct 1185 ms 395072 KB Output is correct

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 392548 KB Output is correct
2 Correct 39 ms 392432 KB Output is correct
3 Correct 38 ms 392456 KB Output is correct
4 Correct 40 ms 392420 KB Output is correct
5 Correct 37 ms 392544 KB Output is correct
6 Correct 37 ms 392544 KB Output is correct
7 Correct 37 ms 392488 KB Output is correct
8 Correct 39 ms 392528 KB Output is correct
9 Correct 39 ms 392528 KB Output is correct
10 Correct 37 ms 392540 KB Output is correct
11 Correct 38 ms 392532 KB Output is correct
12 Correct 38 ms 392532 KB Output is correct
13 Correct 37 ms 392320 KB Output is correct
14 Correct 42 ms 392540 KB Output is correct
15 Correct 39 ms 392460 KB Output is correct
16 Correct 37 ms 392420 KB Output is correct
17 Correct 37 ms 392456 KB Output is correct
18 Correct 37 ms 392528 KB Output is correct
19 Correct 38 ms 392532 KB Output is correct
20 Correct 1092 ms 394716 KB Output is correct
21 Correct 538 ms 394712 KB Output is correct
22 Correct 579 ms 394704 KB Output is correct
23 Correct 613 ms 394580 KB Output is correct
24 Correct 798 ms 394716 KB Output is correct
25 Correct 1161 ms 394832 KB Output is correct
26 Correct 1064 ms 394712 KB Output is correct
27 Correct 1052 ms 394708 KB Output is correct
28 Correct 1065 ms 394712 KB Output is correct
29 Correct 1071 ms 394716 KB Output is correct
30 Correct 1050 ms 394836 KB Output is correct
31 Correct 1072 ms 394832 KB Output is correct
32 Correct 1072 ms 394832 KB Output is correct
33 Correct 1074 ms 394832 KB Output is correct
34 Correct 1058 ms 394820 KB Output is correct
35 Correct 1057 ms 394708 KB Output is correct
36 Correct 38 ms 392532 KB Output is correct
37 Correct 38 ms 392740 KB Output is correct
38 Correct 38 ms 392492 KB Output is correct
39 Execution timed out 5041 ms 404168 KB Time limit exceeded
40 Halted 0 ms 0 KB -