oj.uz

Submission #914363

# Submission time Handle Problem Language Result Execution time Memory
914363 2024-01-21T18:13:52 Z DorostWef Reconstruction Project (JOI22_reconstruction) C++14
100 / 100
 2007 ms 38024 KB 
/*  In the name of GOD */

#include <bits/stdc++.h>

using namespace std;
#define F first
#define S second
#define mk make_pair 
typedef long long ll;
typedef long double ld;
typedef pair <int, int> pii;
const int N = 505, M = 100034, INF = 2000 * 1000 * 1005;
int p[N], sz[N];
ll ans[M * 10];

void reset () {
    for (int i = 0; i < N; i++) {
        p[i] = i;
        sz[i] = 1;
    }
}

int get_par (int v) {
    return (p[v] == v ? v : p[v] = get_par(p[v]));
}

void merge (int u, int v) {
    u = get_par(u);
    v = get_par(v);
    if (u == v)
        return;
    if (sz[u] > sz[v])
        swap (u, v);
    p[u] = v;
    sz[v] += sz[u];
}

struct Edge {
    int u, v, w;
    bool operator< (Edge B) {
        return w < B.w;
    }
} a[M];

int32_t main () {
    ios::sync_with_stdio(false);
    cin.tie();
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
        cin >> a[i].u >> a[i].v >> a[i].w;
    sort (a + 1, a + m + 1);
    vector <int> wef;
    int q;
    cin >> q;
    for (int i = 0; i < q; i++) {
        int x;
        cin >> x;
        wef.push_back(x);
    }
    for (int i = 1; i <= m; i++) {
        a[0].u = a[i].u;
        a[0].v = a[i].v;
        a[0].w = -INF;
        a[m + 1] = a[0];
        a[m + 1].w = INF;
        ll x = -1;
        reset ();
        for (int j = i - 1; j >= 0; j--) {
            merge (a[j].u, a[j].v);
            if (get_par(a[0].u) == get_par(a[0].v)) {
                x = a[j].w;
                break;
            }
        }
        int l = (x + a[i].w + 1) / 2;
        reset ();
        for (int j = i + 1; j <= m + 1; j++) {
            merge (a[j].u, a[j].v);
            if (get_par(a[0].u) == get_par(a[0].v)) {
                x = a[j].w;
                break;
            }
        }
        int r = (x + a[i].w - 1) / 2;
        int in = lower_bound (wef.begin(), wef.end(), l) - wef.begin();
        for (; in < q && wef[in] <= r; in++) {
            ans[in] += abs(wef[in] - a[i].w);
        }
    }
    for (int i = 0; i < q; i++)
        cout << ans[i] << '\n';
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2648 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2508 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2392 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 1 ms 2508 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 1 ms 2396 KB Output is correct
15 Correct 1 ms 2660 KB Output is correct
16 Correct 1 ms 2396 KB Output is correct
17 Correct 1 ms 2396 KB Output is correct
18 Correct 1 ms 2396 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2648 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2508 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2392 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 1 ms 2508 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 1 ms 2396 KB Output is correct
15 Correct 1 ms 2660 KB Output is correct
16 Correct 1 ms 2396 KB Output is correct
17 Correct 1 ms 2396 KB Output is correct
18 Correct 1 ms 2396 KB Output is correct
19 Correct 1 ms 2396 KB Output is correct
20 Correct 1319 ms 4376 KB Output is correct
21 Correct 987 ms 4376 KB Output is correct
22 Correct 1038 ms 4464 KB Output is correct
23 Correct 1159 ms 4368 KB Output is correct
24 Correct 1302 ms 4380 KB Output is correct
25 Correct 1304 ms 4384 KB Output is correct
26 Correct 1331 ms 4372 KB Output is correct
27 Correct 1356 ms 4380 KB Output is correct
28 Correct 1323 ms 4372 KB Output is correct
29 Correct 1333 ms 4384 KB Output is correct
30 Correct 1338 ms 4376 KB Output is correct
31 Correct 1349 ms 4380 KB Output is correct
32 Correct 1347 ms 4384 KB Output is correct
33 Correct 1329 ms 4380 KB Output is correct
34 Correct 1327 ms 4484 KB Output is correct
35 Correct 1331 ms 4376 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 1 ms 2392 KB Output is correct
4 Correct 1809 ms 35872 KB Output is correct
5 Correct 1815 ms 35760 KB Output is correct
6 Correct 1818 ms 35804 KB Output is correct
7 Correct 1272 ms 37664 KB Output is correct
8 Correct 1105 ms 38012 KB Output is correct
9 Correct 1075 ms 37988 KB Output is correct
10 Correct 1791 ms 36120 KB Output is correct
11 Correct 1089 ms 38024 KB Output is correct

Subtask #4
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2648 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2508 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2392 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 1 ms 2508 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 1 ms 2396 KB Output is correct
15 Correct 1 ms 2660 KB Output is correct
16 Correct 1 ms 2396 KB Output is correct
17 Correct 1 ms 2396 KB Output is correct
18 Correct 1 ms 2396 KB Output is correct
19 Correct 1 ms 2396 KB Output is correct
20 Correct 675 ms 35056 KB Output is correct
21 Correct 671 ms 35304 KB Output is correct
22 Correct 693 ms 35392 KB Output is correct
23 Correct 658 ms 35276 KB Output is correct
24 Correct 679 ms 35052 KB Output is correct
25 Correct 664 ms 35116 KB Output is correct
26 Correct 703 ms 35056 KB Output is correct
27 Correct 677 ms 35308 KB Output is correct
28 Correct 697 ms 35172 KB Output is correct
29 Correct 671 ms 35068 KB Output is correct
30 Correct 675 ms 35312 KB Output is correct
31 Correct 679 ms 35036 KB Output is correct
32 Correct 688 ms 35776 KB Output is correct
33 Correct 684 ms 35156 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2648 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2508 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2392 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 1 ms 2508 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 1 ms 2396 KB Output is correct
15 Correct 1 ms 2660 KB Output is correct
16 Correct 1 ms 2396 KB Output is correct
17 Correct 1 ms 2396 KB Output is correct
18 Correct 1 ms 2396 KB Output is correct
19 Correct 1 ms 2396 KB Output is correct
20 Correct 1319 ms 4376 KB Output is correct
21 Correct 987 ms 4376 KB Output is correct
22 Correct 1038 ms 4464 KB Output is correct
23 Correct 1159 ms 4368 KB Output is correct
24 Correct 1302 ms 4380 KB Output is correct
25 Correct 1304 ms 4384 KB Output is correct
26 Correct 1331 ms 4372 KB Output is correct
27 Correct 1356 ms 4380 KB Output is correct
28 Correct 1323 ms 4372 KB Output is correct
29 Correct 1333 ms 4384 KB Output is correct
30 Correct 1338 ms 4376 KB Output is correct
31 Correct 1349 ms 4380 KB Output is correct
32 Correct 1347 ms 4384 KB Output is correct
33 Correct 1329 ms 4380 KB Output is correct
34 Correct 1327 ms 4484 KB Output is correct
35 Correct 1331 ms 4376 KB Output is correct
36 Correct 1343 ms 4944 KB Output is correct
37 Correct 1004 ms 4948 KB Output is correct
38 Correct 1064 ms 4792 KB Output is correct
39 Correct 1195 ms 4788 KB Output is correct
40 Correct 1328 ms 4948 KB Output is correct
41 Correct 1301 ms 4972 KB Output is correct
42 Correct 1327 ms 4916 KB Output is correct
43 Correct 1359 ms 4948 KB Output is correct
44 Correct 1349 ms 4792 KB Output is correct
45 Correct 1324 ms 4948 KB Output is correct
46 Correct 1341 ms 4820 KB Output is correct
47 Correct 1337 ms 4928 KB Output is correct
48 Correct 1345 ms 4776 KB Output is correct
49 Correct 1324 ms 4772 KB Output is correct
50 Correct 1365 ms 5140 KB Output is correct
51 Correct 1339 ms 4788 KB Output is correct

Subtask #6
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2648 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2508 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2392 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 1 ms 2508 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 1 ms 2396 KB Output is correct
15 Correct 1 ms 2660 KB Output is correct
16 Correct 1 ms 2396 KB Output is correct
17 Correct 1 ms 2396 KB Output is correct
18 Correct 1 ms 2396 KB Output is correct
19 Correct 1 ms 2396 KB Output is correct
20 Correct 1319 ms 4376 KB Output is correct
21 Correct 987 ms 4376 KB Output is correct
22 Correct 1038 ms 4464 KB Output is correct
23 Correct 1159 ms 4368 KB Output is correct
24 Correct 1302 ms 4380 KB Output is correct
25 Correct 1304 ms 4384 KB Output is correct
26 Correct 1331 ms 4372 KB Output is correct
27 Correct 1356 ms 4380 KB Output is correct
28 Correct 1323 ms 4372 KB Output is correct
29 Correct 1333 ms 4384 KB Output is correct
30 Correct 1338 ms 4376 KB Output is correct
31 Correct 1349 ms 4380 KB Output is correct
32 Correct 1347 ms 4384 KB Output is correct
33 Correct 1329 ms 4380 KB Output is correct
34 Correct 1327 ms 4484 KB Output is correct
35 Correct 1331 ms 4376 KB Output is correct
36 Correct 1 ms 2392 KB Output is correct
37 Correct 1 ms 2392 KB Output is correct
38 Correct 1 ms 2392 KB Output is correct
39 Correct 1809 ms 35872 KB Output is correct
40 Correct 1815 ms 35760 KB Output is correct
41 Correct 1818 ms 35804 KB Output is correct
42 Correct 1272 ms 37664 KB Output is correct
43 Correct 1105 ms 38012 KB Output is correct
44 Correct 1075 ms 37988 KB Output is correct
45 Correct 1791 ms 36120 KB Output is correct
46 Correct 1089 ms 38024 KB Output is correct
47 Correct 1 ms 2396 KB Output is correct
48 Correct 675 ms 35056 KB Output is correct
49 Correct 671 ms 35304 KB Output is correct
50 Correct 693 ms 35392 KB Output is correct
51 Correct 658 ms 35276 KB Output is correct
52 Correct 679 ms 35052 KB Output is correct
53 Correct 664 ms 35116 KB Output is correct
54 Correct 703 ms 35056 KB Output is correct
55 Correct 677 ms 35308 KB Output is correct
56 Correct 697 ms 35172 KB Output is correct
57 Correct 671 ms 35068 KB Output is correct
58 Correct 675 ms 35312 KB Output is correct
59 Correct 679 ms 35036 KB Output is correct
60 Correct 688 ms 35776 KB Output is correct
61 Correct 684 ms 35156 KB Output is correct
62 Correct 1343 ms 4944 KB Output is correct
63 Correct 1004 ms 4948 KB Output is correct
64 Correct 1064 ms 4792 KB Output is correct
65 Correct 1195 ms 4788 KB Output is correct
66 Correct 1328 ms 4948 KB Output is correct
67 Correct 1301 ms 4972 KB Output is correct
68 Correct 1327 ms 4916 KB Output is correct
69 Correct 1359 ms 4948 KB Output is correct
70 Correct 1349 ms 4792 KB Output is correct
71 Correct 1324 ms 4948 KB Output is correct
72 Correct 1341 ms 4820 KB Output is correct
73 Correct 1337 ms 4928 KB Output is correct
74 Correct 1345 ms 4776 KB Output is correct
75 Correct 1324 ms 4772 KB Output is correct
76 Correct 1365 ms 5140 KB Output is correct
77 Correct 1339 ms 4788 KB Output is correct
78 Correct 1970 ms 34928 KB Output is correct
79 Correct 1636 ms 36896 KB Output is correct
80 Correct 1712 ms 36020 KB Output is correct
81 Correct 1834 ms 35768 KB Output is correct
82 Correct 2007 ms 35004 KB Output is correct
83 Correct 1967 ms 34900 KB Output is correct
84 Correct 1944 ms 34752 KB Output is correct
85 Correct 1997 ms 34880 KB Output is correct
86 Correct 1979 ms 34748 KB Output is correct
87 Correct 1971 ms 36464 KB Output is correct
88 Correct 1963 ms 34736 KB Output is correct
89 Correct 1995 ms 34732 KB Output is correct
90 Correct 1971 ms 34848 KB Output is correct
91 Correct 1974 ms 34752 KB Output is correct
92 Correct 1988 ms 37664 KB Output is correct
93 Correct 1996 ms 35980 KB Output is correct