oj.uz

Submission #544942

# Submission time Handle Problem Language Result Execution time Memory
544942 2022-04-03T07:50:38 Z benson1029 Reconstruction Project (JOI22_reconstruction) C++14
70 / 100
 5000 ms 827312 KB 
#include<bits/stdc++.h>
using namespace std;

int n, m, q;
pair< int, pair<int,int> > edg[100005];
vector<int> f[100005], b[100005], t[100005];
int x[100005], y[100005];
int dsu[100005];

int find(int x) {
	if(dsu[x]==x) return x;
	return dsu[x] = find(dsu[x]);
}

void merge(int x) {
	dsu[find(edg[x].second.first)] = find(edg[x].second.second);
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> m;
	for(int i=1; i<=m; i++) {
		cin >> edg[i].second.first >> edg[i].second.second >> edg[i].first;
	}
	sort(edg+1, edg+m+1);
	for(int i=1; i<=m; i++) {
		b[i].push_back(i);
		for(int j=1; j<=n; j++) dsu[j] = j;
		bool tmp = false;
		x[i] = -1;
		for(int j:b[i-1]) {
			if(find(edg[j].second.first)!=find(edg[j].second.second)) {
				merge(j);
				if(find(edg[i].second.first)==find(edg[i].second.second) && !tmp) {
					tmp = true;
					x[i] = (edg[j].first + edg[i].first + 2) / 2;
				}
				else b[i].push_back(j);
			}
		}
	}
	for(int i=m; i>=1; i--) {
		f[i].push_back(i);
		for(int j=1; j<=n; j++) dsu[j] = j;
		bool tmp = false;
		y[i] = 2e9;
		for(int j:f[i+1]) {
			if(find(edg[j].second.first)!=find(edg[j].second.second)) {
				merge(j);
				if(find(edg[i].second.first)==find(edg[i].second.second) && !tmp) {
					tmp = true;
					y[i] = (edg[j].first + edg[i].first) / 2;
				}
				else f[i].push_back(j);
			}
		}
	}
	for(int i=0; i<=m; i++) {
		for(int j:b[i]) t[i].push_back(j);
		for(int j:f[i+1]) t[i].push_back(j);
	}
	cin >> q;
	while(q--) {
		int v;
		cin >> v;
		int pos = upper_bound(edg+1, edg+m+1, make_pair(v, make_pair((int)1e9, (int)1e9))) - edg - 1;
		long long ans = 0;
		for(int i:t[pos]) {
			if(v>=x[i] && v<=y[i]) {
				ans += abs(v-edg[i].first);
			}
		}
		cout << ans << "\n";
	}
}

Subtask #1
3.0 / 3.0

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

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 4 ms 7380 KB Output is correct
3 Correct 5 ms 7380 KB Output is correct
4 Correct 4 ms 7380 KB Output is correct
5 Correct 4 ms 7380 KB Output is correct
6 Correct 4 ms 7380 KB Output is correct
7 Correct 5 ms 7380 KB Output is correct
8 Correct 4 ms 7376 KB Output is correct
9 Correct 4 ms 7380 KB Output is correct
10 Correct 4 ms 7380 KB Output is correct
11 Correct 4 ms 7380 KB Output is correct
12 Correct 4 ms 7380 KB Output is correct
13 Correct 4 ms 7380 KB Output is correct
14 Correct 5 ms 7380 KB Output is correct
15 Correct 4 ms 7380 KB Output is correct
16 Correct 4 ms 7380 KB Output is correct
17 Correct 4 ms 7380 KB Output is correct
18 Correct 5 ms 7380 KB Output is correct
19 Correct 4 ms 7380 KB Output is correct
20 Correct 4242 ms 816048 KB Output is correct
21 Correct 3210 ms 814772 KB Output is correct
22 Correct 3393 ms 814516 KB Output is correct
23 Correct 3551 ms 814672 KB Output is correct
24 Correct 3980 ms 814792 KB Output is correct
25 Correct 4390 ms 815040 KB Output is correct
26 Correct 4255 ms 815940 KB Output is correct
27 Correct 4258 ms 815820 KB Output is correct
28 Correct 4233 ms 815660 KB Output is correct
29 Correct 3870 ms 812132 KB Output is correct
30 Correct 4306 ms 815032 KB Output is correct
31 Correct 4365 ms 815296 KB Output is correct
32 Correct 4267 ms 815204 KB Output is correct
33 Correct 4275 ms 814984 KB Output is correct
34 Correct 3056 ms 785172 KB Output is correct
35 Correct 4266 ms 815056 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 4 ms 7380 KB Output is correct
3 Correct 4 ms 7380 KB Output is correct
4 Execution timed out 5074 ms 827312 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 4 ms 7380 KB Output is correct
3 Correct 5 ms 7380 KB Output is correct
4 Correct 4 ms 7380 KB Output is correct
5 Correct 4 ms 7380 KB Output is correct
6 Correct 4 ms 7380 KB Output is correct
7 Correct 5 ms 7380 KB Output is correct
8 Correct 4 ms 7376 KB Output is correct
9 Correct 4 ms 7380 KB Output is correct
10 Correct 4 ms 7380 KB Output is correct
11 Correct 4 ms 7380 KB Output is correct
12 Correct 4 ms 7380 KB Output is correct
13 Correct 4 ms 7380 KB Output is correct
14 Correct 5 ms 7380 KB Output is correct
15 Correct 4 ms 7380 KB Output is correct
16 Correct 4 ms 7380 KB Output is correct
17 Correct 4 ms 7380 KB Output is correct
18 Correct 5 ms 7380 KB Output is correct
19 Correct 4 ms 7380 KB Output is correct
20 Correct 1500 ms 30724 KB Output is correct
21 Correct 1398 ms 27644 KB Output is correct
22 Correct 1329 ms 30224 KB Output is correct
23 Correct 1314 ms 30268 KB Output is correct
24 Correct 1324 ms 30188 KB Output is correct
25 Correct 1327 ms 30232 KB Output is correct
26 Correct 1306 ms 30080 KB Output is correct
27 Correct 1285 ms 30200 KB Output is correct
28 Correct 1344 ms 30240 KB Output is correct
29 Correct 1339 ms 30276 KB Output is correct
30 Correct 1335 ms 27668 KB Output is correct
31 Correct 1361 ms 30460 KB Output is correct
32 Correct 1025 ms 30608 KB Output is correct
33 Correct 1560 ms 29904 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 4 ms 7380 KB Output is correct
3 Correct 5 ms 7380 KB Output is correct
4 Correct 4 ms 7380 KB Output is correct
5 Correct 4 ms 7380 KB Output is correct
6 Correct 4 ms 7380 KB Output is correct
7 Correct 5 ms 7380 KB Output is correct
8 Correct 4 ms 7376 KB Output is correct
9 Correct 4 ms 7380 KB Output is correct
10 Correct 4 ms 7380 KB Output is correct
11 Correct 4 ms 7380 KB Output is correct
12 Correct 4 ms 7380 KB Output is correct
13 Correct 4 ms 7380 KB Output is correct
14 Correct 5 ms 7380 KB Output is correct
15 Correct 4 ms 7380 KB Output is correct
16 Correct 4 ms 7380 KB Output is correct
17 Correct 4 ms 7380 KB Output is correct
18 Correct 5 ms 7380 KB Output is correct
19 Correct 4 ms 7380 KB Output is correct
20 Correct 4242 ms 816048 KB Output is correct
21 Correct 3210 ms 814772 KB Output is correct
22 Correct 3393 ms 814516 KB Output is correct
23 Correct 3551 ms 814672 KB Output is correct
24 Correct 3980 ms 814792 KB Output is correct
25 Correct 4390 ms 815040 KB Output is correct
26 Correct 4255 ms 815940 KB Output is correct
27 Correct 4258 ms 815820 KB Output is correct
28 Correct 4233 ms 815660 KB Output is correct
29 Correct 3870 ms 812132 KB Output is correct
30 Correct 4306 ms 815032 KB Output is correct
31 Correct 4365 ms 815296 KB Output is correct
32 Correct 4267 ms 815204 KB Output is correct
33 Correct 4275 ms 814984 KB Output is correct
34 Correct 3056 ms 785172 KB Output is correct
35 Correct 4266 ms 815056 KB Output is correct
36 Correct 4315 ms 815036 KB Output is correct
37 Correct 3375 ms 814920 KB Output is correct
38 Correct 3532 ms 814812 KB Output is correct
39 Correct 3634 ms 814936 KB Output is correct
40 Correct 4090 ms 814824 KB Output is correct
41 Correct 4512 ms 814916 KB Output is correct
42 Correct 4364 ms 815072 KB Output is correct
43 Correct 4329 ms 815196 KB Output is correct
44 Correct 4289 ms 815072 KB Output is correct
45 Correct 3953 ms 811944 KB Output is correct
46 Correct 4251 ms 814920 KB Output is correct
47 Correct 4280 ms 815020 KB Output is correct
48 Correct 4288 ms 814996 KB Output is correct
49 Correct 4286 ms 815052 KB Output is correct
50 Correct 3033 ms 785136 KB Output is correct
51 Correct 4277 ms 814992 KB Output is correct

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 4 ms 7380 KB Output is correct
3 Correct 5 ms 7380 KB Output is correct
4 Correct 4 ms 7380 KB Output is correct
5 Correct 4 ms 7380 KB Output is correct
6 Correct 4 ms 7380 KB Output is correct
7 Correct 5 ms 7380 KB Output is correct
8 Correct 4 ms 7376 KB Output is correct
9 Correct 4 ms 7380 KB Output is correct
10 Correct 4 ms 7380 KB Output is correct
11 Correct 4 ms 7380 KB Output is correct
12 Correct 4 ms 7380 KB Output is correct
13 Correct 4 ms 7380 KB Output is correct
14 Correct 5 ms 7380 KB Output is correct
15 Correct 4 ms 7380 KB Output is correct
16 Correct 4 ms 7380 KB Output is correct
17 Correct 4 ms 7380 KB Output is correct
18 Correct 5 ms 7380 KB Output is correct
19 Correct 4 ms 7380 KB Output is correct
20 Correct 4242 ms 816048 KB Output is correct
21 Correct 3210 ms 814772 KB Output is correct
22 Correct 3393 ms 814516 KB Output is correct
23 Correct 3551 ms 814672 KB Output is correct
24 Correct 3980 ms 814792 KB Output is correct
25 Correct 4390 ms 815040 KB Output is correct
26 Correct 4255 ms 815940 KB Output is correct
27 Correct 4258 ms 815820 KB Output is correct
28 Correct 4233 ms 815660 KB Output is correct
29 Correct 3870 ms 812132 KB Output is correct
30 Correct 4306 ms 815032 KB Output is correct
31 Correct 4365 ms 815296 KB Output is correct
32 Correct 4267 ms 815204 KB Output is correct
33 Correct 4275 ms 814984 KB Output is correct
34 Correct 3056 ms 785172 KB Output is correct
35 Correct 4266 ms 815056 KB Output is correct
36 Correct 4 ms 7380 KB Output is correct
37 Correct 4 ms 7380 KB Output is correct
38 Correct 4 ms 7380 KB Output is correct
39 Execution timed out 5074 ms 827312 KB Time limit exceeded
40 Halted 0 ms 0 KB -