oj.uz

Submission #751886

# Submission time Handle Problem Language Result Execution time Memory
751886 2023-06-01T17:30:38 Z puppy Reconstruction Project (JOI22_reconstruction) C++17
100 / 100
 1267 ms 17268 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cassert>
#define all(v) v.begin(), v.end()
using namespace std;
int N, M;
int stop[100005];

struct Edge
{
    int s, e;
    int w;
    bool operator<(const Edge &e)
    {
        return w < e.w;
    }
};
Edge edge[100005];
vector<pair<int, int>> adj[505];
bool visited[505];
pair<int, int> par[505];
bool add[100005];
signed main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> N >> M;
    for (int i = 1; i <= M; i++) {
        int a, b, w; cin >> a >> b >> w;
        edge[i] = {a, b, w};
    }
    sort(edge + 1, edge + M + 1);
    for (int i = 1; i <= M; i++) {
        fill(visited + 1, visited + N + 1, false);
        int a = edge[i].s, b = edge[i].e;
        visited[a] = true;
        queue<int> q;
        q.push(a);
        while (!q.empty()) {
            int cur = q.front(); q.pop();
            for (pair<int, int> p:adj[cur]) {
                if (!visited[p.second]) {
                    par[p.second] = make_pair(p.first, cur);
                    visited[p.second] = true; q.push(p.second);
                }
            }
        }
        if (visited[b]) {
            int mn = i, now = b;
            while (1) {
                mn = min(mn, par[now].first);
                now = par[now].second;
                if (now == a) break;
            }
            int s = edge[mn].s, e = edge[mn].e;
            adj[s].erase(remove(all(adj[s]), make_pair(mn, e)), adj[s].end());
            adj[e].erase(remove(all(adj[e]), make_pair(mn, s)), adj[e].end());
            stop[mn] = i;
            add[i] = true;
        }
        adj[a].push_back(make_pair(i, b));
        adj[b].push_back(make_pair(i, a));
    }
    vector<pair<int, pair<int, int>>> vc;
    for (int i = 1; i <= M; i++) {
        if (stop[i]) {
            vc.push_back(make_pair((edge[i].w+edge[stop[i]].w)/2+1, make_pair(i, stop[i])));
        }
    }
    sort(vc.begin(), vc.end());
    int pv = 0;
    int pv2 = 0;
    int Q; cin >> Q;
    pair<long long, long long> lin = make_pair(0LL, 0LL);
    for (int i = 1; i <= M; i++) {
        if (!add[i]) {
            lin.first -= 1;
            lin.second += edge[i].w;
        }
    }
    for (int i = 0; i < Q; i++) {
        long long X; cin >> X;
        while (pv < M && edge[pv+1].w <= X) {
            pv++;
            lin.second -= 2 * edge[pv].w;
            lin.first += 2;
        }
        while (pv2 < (int)vc.size() && vc[pv2].first <= X) {
            lin.first -= 2;
            lin.second += edge[vc[pv2].second.first].w + edge[vc[pv2].second.second].w;
            pv2++;
        }
        cout << X * lin.first + lin.second << '\n';
    }
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 244 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 344 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 0 ms 340 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 244 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 344 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 0 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1027 ms 4124 KB Output is correct
21 Correct 535 ms 4132 KB Output is correct
22 Correct 844 ms 4064 KB Output is correct
23 Correct 954 ms 4144 KB Output is correct
24 Correct 984 ms 4216 KB Output is correct
25 Correct 1089 ms 4080 KB Output is correct
26 Correct 1064 ms 4196 KB Output is correct
27 Correct 1099 ms 4032 KB Output is correct
28 Correct 1110 ms 4008 KB Output is correct
29 Correct 1128 ms 4052 KB Output is correct
30 Correct 1091 ms 4152 KB Output is correct
31 Correct 1072 ms 4028 KB Output is correct
32 Correct 1083 ms 4072 KB Output is correct
33 Correct 1065 ms 4112 KB Output is correct
34 Correct 1096 ms 4124 KB Output is correct
35 Correct 1055 ms 4000 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 971 ms 16140 KB Output is correct
5 Correct 991 ms 15100 KB Output is correct
6 Correct 958 ms 15212 KB Output is correct
7 Correct 259 ms 17008 KB Output is correct
8 Correct 237 ms 17144 KB Output is correct
9 Correct 257 ms 17088 KB Output is correct
10 Correct 991 ms 15080 KB Output is correct
11 Correct 236 ms 17268 KB Output is correct

Subtask #4
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 244 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 344 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 0 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 196 ms 13804 KB Output is correct
21 Correct 190 ms 13536 KB Output is correct
22 Correct 199 ms 13384 KB Output is correct
23 Correct 200 ms 13388 KB Output is correct
24 Correct 186 ms 13360 KB Output is correct
25 Correct 202 ms 13388 KB Output is correct
26 Correct 169 ms 13312 KB Output is correct
27 Correct 186 ms 13432 KB Output is correct
28 Correct 183 ms 13396 KB Output is correct
29 Correct 175 ms 13356 KB Output is correct
30 Correct 186 ms 13392 KB Output is correct
31 Correct 178 ms 13348 KB Output is correct
32 Correct 171 ms 13900 KB Output is correct
33 Correct 173 ms 13260 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 244 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 344 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 0 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1027 ms 4124 KB Output is correct
21 Correct 535 ms 4132 KB Output is correct
22 Correct 844 ms 4064 KB Output is correct
23 Correct 954 ms 4144 KB Output is correct
24 Correct 984 ms 4216 KB Output is correct
25 Correct 1089 ms 4080 KB Output is correct
26 Correct 1064 ms 4196 KB Output is correct
27 Correct 1099 ms 4032 KB Output is correct
28 Correct 1110 ms 4008 KB Output is correct
29 Correct 1128 ms 4052 KB Output is correct
30 Correct 1091 ms 4152 KB Output is correct
31 Correct 1072 ms 4028 KB Output is correct
32 Correct 1083 ms 4072 KB Output is correct
33 Correct 1065 ms 4112 KB Output is correct
34 Correct 1096 ms 4124 KB Output is correct
35 Correct 1055 ms 4000 KB Output is correct
36 Correct 1026 ms 4032 KB Output is correct
37 Correct 547 ms 4120 KB Output is correct
38 Correct 933 ms 4080 KB Output is correct
39 Correct 1016 ms 4088 KB Output is correct
40 Correct 1090 ms 4080 KB Output is correct
41 Correct 1108 ms 4020 KB Output is correct
42 Correct 1098 ms 4044 KB Output is correct
43 Correct 1050 ms 4224 KB Output is correct
44 Correct 1086 ms 4008 KB Output is correct
45 Correct 1075 ms 4168 KB Output is correct
46 Correct 1033 ms 4088 KB Output is correct
47 Correct 1040 ms 4188 KB Output is correct
48 Correct 1016 ms 4080 KB Output is correct
49 Correct 1036 ms 4108 KB Output is correct
50 Correct 1036 ms 4096 KB Output is correct
51 Correct 1047 ms 4012 KB Output is correct

Subtask #6
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 244 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 344 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 0 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1027 ms 4124 KB Output is correct
21 Correct 535 ms 4132 KB Output is correct
22 Correct 844 ms 4064 KB Output is correct
23 Correct 954 ms 4144 KB Output is correct
24 Correct 984 ms 4216 KB Output is correct
25 Correct 1089 ms 4080 KB Output is correct
26 Correct 1064 ms 4196 KB Output is correct
27 Correct 1099 ms 4032 KB Output is correct
28 Correct 1110 ms 4008 KB Output is correct
29 Correct 1128 ms 4052 KB Output is correct
30 Correct 1091 ms 4152 KB Output is correct
31 Correct 1072 ms 4028 KB Output is correct
32 Correct 1083 ms 4072 KB Output is correct
33 Correct 1065 ms 4112 KB Output is correct
34 Correct 1096 ms 4124 KB Output is correct
35 Correct 1055 ms 4000 KB Output is correct
36 Correct 1 ms 340 KB Output is correct
37 Correct 1 ms 340 KB Output is correct
38 Correct 0 ms 340 KB Output is correct
39 Correct 971 ms 16140 KB Output is correct
40 Correct 991 ms 15100 KB Output is correct
41 Correct 958 ms 15212 KB Output is correct
42 Correct 259 ms 17008 KB Output is correct
43 Correct 237 ms 17144 KB Output is correct
44 Correct 257 ms 17088 KB Output is correct
45 Correct 991 ms 15080 KB Output is correct
46 Correct 236 ms 17268 KB Output is correct
47 Correct 1 ms 340 KB Output is correct
48 Correct 196 ms 13804 KB Output is correct
49 Correct 190 ms 13536 KB Output is correct
50 Correct 199 ms 13384 KB Output is correct
51 Correct 200 ms 13388 KB Output is correct
52 Correct 186 ms 13360 KB Output is correct
53 Correct 202 ms 13388 KB Output is correct
54 Correct 169 ms 13312 KB Output is correct
55 Correct 186 ms 13432 KB Output is correct
56 Correct 183 ms 13396 KB Output is correct
57 Correct 175 ms 13356 KB Output is correct
58 Correct 186 ms 13392 KB Output is correct
59 Correct 178 ms 13348 KB Output is correct
60 Correct 171 ms 13900 KB Output is correct
61 Correct 173 ms 13260 KB Output is correct
62 Correct 1026 ms 4032 KB Output is correct
63 Correct 547 ms 4120 KB Output is correct
64 Correct 933 ms 4080 KB Output is correct
65 Correct 1016 ms 4088 KB Output is correct
66 Correct 1090 ms 4080 KB Output is correct
67 Correct 1108 ms 4020 KB Output is correct
68 Correct 1098 ms 4044 KB Output is correct
69 Correct 1050 ms 4224 KB Output is correct
70 Correct 1086 ms 4008 KB Output is correct
71 Correct 1075 ms 4168 KB Output is correct
72 Correct 1033 ms 4088 KB Output is correct
73 Correct 1040 ms 4188 KB Output is correct
74 Correct 1016 ms 4080 KB Output is correct
75 Correct 1036 ms 4108 KB Output is correct
76 Correct 1036 ms 4096 KB Output is correct
77 Correct 1047 ms 4012 KB Output is correct
78 Correct 1212 ms 14212 KB Output is correct
79 Correct 647 ms 16168 KB Output is correct
80 Correct 1004 ms 15380 KB Output is correct
81 Correct 1098 ms 15112 KB Output is correct
82 Correct 1162 ms 14276 KB Output is correct
83 Correct 1184 ms 14084 KB Output is correct
84 Correct 1170 ms 14140 KB Output is correct
85 Correct 1220 ms 14152 KB Output is correct
86 Correct 1211 ms 14148 KB Output is correct
87 Correct 1239 ms 15772 KB Output is correct
88 Correct 1267 ms 14092 KB Output is correct
89 Correct 1239 ms 14128 KB Output is correct
90 Correct 1191 ms 14128 KB Output is correct
91 Correct 1198 ms 13688 KB Output is correct
92 Correct 1195 ms 16452 KB Output is correct
93 Correct 1192 ms 14764 KB Output is correct