Submission #544938

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
544938	2022-04-03T07:45:19 Z	benson1029	Reconstruction Project (JOI22_reconstruction)	C++14	70 / 100	5000 ms	830108 KB

reconstruction

#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);
}

bool ok(int p, int v) {
	return ((x[p]==-1 || v>=x[p]) && (y[p]==-1 || v<=y[p]));
}

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] = -1;
		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(ok(i, v)) {
				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	3 ms	7380 KB	Output is correct
3	Correct	4 ms	7380 KB	Output is correct
4	Correct	4 ms	7380 KB	Output is correct
5	Correct	3 ms	7380 KB	Output is correct
6	Correct	4 ms	7380 KB	Output is correct
7	Correct	4 ms	7380 KB	Output is correct
8	Correct	3 ms	7380 KB	Output is correct
9	Correct	4 ms	7380 KB	Output is correct
10	Correct	3 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	7372 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	4 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	3 ms	7380 KB	Output is correct
3	Correct	4 ms	7380 KB	Output is correct
4	Correct	4 ms	7380 KB	Output is correct
5	Correct	3 ms	7380 KB	Output is correct
6	Correct	4 ms	7380 KB	Output is correct
7	Correct	4 ms	7380 KB	Output is correct
8	Correct	3 ms	7380 KB	Output is correct
9	Correct	4 ms	7380 KB	Output is correct
10	Correct	3 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	7372 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	4 ms	7380 KB	Output is correct
19	Correct	4 ms	7328 KB	Output is correct
20	Correct	4296 ms	814920 KB	Output is correct
21	Correct	3201 ms	814676 KB	Output is correct
22	Correct	3402 ms	814572 KB	Output is correct
23	Correct	3544 ms	814704 KB	Output is correct
24	Correct	4033 ms	814764 KB	Output is correct
25	Correct	4583 ms	814772 KB	Output is correct
26	Correct	4677 ms	815556 KB	Output is correct
27	Correct	4664 ms	815660 KB	Output is correct
28	Correct	4542 ms	815736 KB	Output is correct
29	Correct	4167 ms	813008 KB	Output is correct
30	Correct	4525 ms	816072 KB	Output is correct
31	Correct	4283 ms	816092 KB	Output is correct
32	Correct	4278 ms	816228 KB	Output is correct
33	Correct	4296 ms	814812 KB	Output is correct
34	Correct	3054 ms	786152 KB	Output is correct
35	Correct	4295 ms	815916 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	5099 ms	830108 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	3 ms	7380 KB	Output is correct
3	Correct	4 ms	7380 KB	Output is correct
4	Correct	4 ms	7380 KB	Output is correct
5	Correct	3 ms	7380 KB	Output is correct
6	Correct	4 ms	7380 KB	Output is correct
7	Correct	4 ms	7380 KB	Output is correct
8	Correct	3 ms	7380 KB	Output is correct
9	Correct	4 ms	7380 KB	Output is correct
10	Correct	3 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	7372 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	4 ms	7380 KB	Output is correct
19	Correct	4 ms	7380 KB	Output is correct
20	Correct	1866 ms	33856 KB	Output is correct
21	Correct	1827 ms	31516 KB	Output is correct
22	Correct	1823 ms	36316 KB	Output is correct
23	Correct	1853 ms	36840 KB	Output is correct
24	Correct	1839 ms	36616 KB	Output is correct
25	Correct	1839 ms	36616 KB	Output is correct
26	Correct	1860 ms	36860 KB	Output is correct
27	Correct	1797 ms	36608 KB	Output is correct
28	Correct	1885 ms	36784 KB	Output is correct
29	Correct	1824 ms	36660 KB	Output is correct
30	Correct	1766 ms	36864 KB	Output is correct
31	Correct	1934 ms	36396 KB	Output is correct
32	Correct	1896 ms	37152 KB	Output is correct
33	Correct	2147 ms	36468 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	3 ms	7380 KB	Output is correct
3	Correct	4 ms	7380 KB	Output is correct
4	Correct	4 ms	7380 KB	Output is correct
5	Correct	3 ms	7380 KB	Output is correct
6	Correct	4 ms	7380 KB	Output is correct
7	Correct	4 ms	7380 KB	Output is correct
8	Correct	3 ms	7380 KB	Output is correct
9	Correct	4 ms	7380 KB	Output is correct
10	Correct	3 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	7372 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	4 ms	7380 KB	Output is correct
19	Correct	4 ms	7328 KB	Output is correct
20	Correct	4296 ms	814920 KB	Output is correct
21	Correct	3201 ms	814676 KB	Output is correct
22	Correct	3402 ms	814572 KB	Output is correct
23	Correct	3544 ms	814704 KB	Output is correct
24	Correct	4033 ms	814764 KB	Output is correct
25	Correct	4583 ms	814772 KB	Output is correct
26	Correct	4677 ms	815556 KB	Output is correct
27	Correct	4664 ms	815660 KB	Output is correct
28	Correct	4542 ms	815736 KB	Output is correct
29	Correct	4167 ms	813008 KB	Output is correct
30	Correct	4525 ms	816072 KB	Output is correct
31	Correct	4283 ms	816092 KB	Output is correct
32	Correct	4278 ms	816228 KB	Output is correct
33	Correct	4296 ms	814812 KB	Output is correct
34	Correct	3054 ms	786152 KB	Output is correct
35	Correct	4295 ms	815916 KB	Output is correct
36	Correct	4356 ms	815060 KB	Output is correct
37	Correct	3316 ms	814920 KB	Output is correct
38	Correct	3488 ms	814952 KB	Output is correct
39	Correct	3631 ms	814888 KB	Output is correct
40	Correct	4083 ms	814924 KB	Output is correct
41	Correct	4496 ms	815072 KB	Output is correct
42	Correct	4463 ms	815164 KB	Output is correct
43	Correct	4355 ms	815124 KB	Output is correct
44	Correct	4372 ms	814996 KB	Output is correct
45	Correct	3922 ms	811896 KB	Output is correct
46	Correct	4328 ms	815072 KB	Output is correct
47	Correct	4309 ms	815236 KB	Output is correct
48	Correct	4294 ms	815288 KB	Output is correct
49	Correct	4282 ms	815220 KB	Output is correct
50	Correct	3159 ms	784928 KB	Output is correct
51	Correct	4586 ms	815096 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	3 ms	7380 KB	Output is correct
3	Correct	4 ms	7380 KB	Output is correct
4	Correct	4 ms	7380 KB	Output is correct
5	Correct	3 ms	7380 KB	Output is correct
6	Correct	4 ms	7380 KB	Output is correct
7	Correct	4 ms	7380 KB	Output is correct
8	Correct	3 ms	7380 KB	Output is correct
9	Correct	4 ms	7380 KB	Output is correct
10	Correct	3 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	7372 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	4 ms	7380 KB	Output is correct
19	Correct	4 ms	7328 KB	Output is correct
20	Correct	4296 ms	814920 KB	Output is correct
21	Correct	3201 ms	814676 KB	Output is correct
22	Correct	3402 ms	814572 KB	Output is correct
23	Correct	3544 ms	814704 KB	Output is correct
24	Correct	4033 ms	814764 KB	Output is correct
25	Correct	4583 ms	814772 KB	Output is correct
26	Correct	4677 ms	815556 KB	Output is correct
27	Correct	4664 ms	815660 KB	Output is correct
28	Correct	4542 ms	815736 KB	Output is correct
29	Correct	4167 ms	813008 KB	Output is correct
30	Correct	4525 ms	816072 KB	Output is correct
31	Correct	4283 ms	816092 KB	Output is correct
32	Correct	4278 ms	816228 KB	Output is correct
33	Correct	4296 ms	814812 KB	Output is correct
34	Correct	3054 ms	786152 KB	Output is correct
35	Correct	4295 ms	815916 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	5099 ms	830108 KB	Time limit exceeded
40	Halted	0 ms	0 KB	-

Submission #544938

Compilation message

Subtask #1 3.0 / 3.0

Subtask #2 4.0 / 4.0

Subtask #3 0 / 7.0

Subtask #4 28.0 / 28.0

Subtask #5 35.0 / 35.0

Subtask #6 0 / 23.0

Subtask #1
3.0 / 3.0

Subtask #2
4.0 / 4.0

Subtask #3
0 / 7.0

Subtask #4
28.0 / 28.0

Subtask #5
35.0 / 35.0

Subtask #6
0 / 23.0