oj.uz

Submission #544958

# Submission time Handle Problem Language Result Execution time Memory
544958 2022-04-03T08:26:42 Z benson1029 Reconstruction Project (JOI22_reconstruction) C++14
100 / 100
 4103 ms 436708 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];
vector< pair<int,int> > v;
multiset<int> sm, lg; long long sm_sum = 0, lg_sum = 0;

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=1; i<=m; i++) {
		if(x[i] <= y[i]) {
			v.push_back({x[i], edg[i].first});
			v.push_back({y[i]+1, -edg[i].first});
		}
	}
	sort(v.begin(), v.end());
	long long ans = 0;
	int ptr = 0;
	cin >> q;
	while(q--) {
		int w;
		cin >> w;
		while(!lg.empty() && (*lg.begin()) <= w) {
			sm_sum += (*lg.begin());
			lg_sum -= (*lg.begin());
			sm.insert(*lg.begin());
			lg.erase(lg.begin());
		}
		while(ptr < v.size() && v[ptr].first <= w) {
			if(abs(v[ptr].second) <= w) {
				sm_sum += v[ptr].second;
				if(v[ptr].second>0) sm.insert(v[ptr].second);
				else sm.erase(sm.find(-v[ptr].second));
			} else {
				lg_sum += v[ptr].second;
				if(v[ptr].second>0) lg.insert(v[ptr].second);
				else lg.erase(lg.find(-v[ptr].second));
			}
			ptr++;
		}
		cout << (w*sm.size() - sm_sum) + (lg_sum - w*lg.size()) << "\n";
	}
}

Compilation message

reconstruction.cpp: In function 'int main()':
reconstruction.cpp:80:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |   while(ptr < v.size() && v[ptr].first <= w) {
      |         ~~~~^~~~~~~~~~
reconstruction.cpp:68:12: warning: unused variable 'ans' [-Wunused-variable]
   68 |  long long ans = 0;
      |            ^~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 3 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 Correct 3 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 3 ms 7380 KB Output is correct
8 Correct 4 ms 7380 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 5 ms 7380 KB Output is correct
13 Correct 4 ms 7264 KB Output is correct
14 Correct 4 ms 7380 KB Output is correct
15 Correct 4 ms 7352 KB Output is correct
16 Correct 5 ms 7380 KB Output is correct
17 Correct 5 ms 7332 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 3 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 Correct 3 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 3 ms 7380 KB Output is correct
8 Correct 4 ms 7380 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 5 ms 7380 KB Output is correct
13 Correct 4 ms 7264 KB Output is correct
14 Correct 4 ms 7380 KB Output is correct
15 Correct 4 ms 7352 KB Output is correct
16 Correct 5 ms 7380 KB Output is correct
17 Correct 5 ms 7332 KB Output is correct
18 Correct 4 ms 7380 KB Output is correct
19 Correct 4 ms 7380 KB Output is correct
20 Correct 3900 ms 414904 KB Output is correct
21 Correct 2794 ms 414608 KB Output is correct
22 Correct 2950 ms 414600 KB Output is correct
23 Correct 3096 ms 414528 KB Output is correct
24 Correct 3606 ms 414624 KB Output is correct
25 Correct 4057 ms 414744 KB Output is correct
26 Correct 3917 ms 414884 KB Output is correct
27 Correct 3932 ms 414800 KB Output is correct
28 Correct 3854 ms 414624 KB Output is correct
29 Correct 3456 ms 409952 KB Output is correct
30 Correct 3971 ms 414732 KB Output is correct
31 Correct 3930 ms 414708 KB Output is correct
32 Correct 3989 ms 414700 KB Output is correct
33 Correct 3908 ms 414624 KB Output is correct
34 Correct 2580 ms 382640 KB Output is correct
35 Correct 3951 ms 414704 KB Output is correct

Subtask #3
7.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 Correct 3249 ms 426456 KB Output is correct
5 Correct 3255 ms 436228 KB Output is correct
6 Correct 3067 ms 436452 KB Output is correct
7 Correct 1949 ms 352192 KB Output is correct
8 Correct 1789 ms 315664 KB Output is correct
9 Correct 1726 ms 304656 KB Output is correct
10 Correct 3013 ms 436708 KB Output is correct
11 Correct 1799 ms 309788 KB Output is correct

Subtask #4
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 3 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 Correct 3 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 3 ms 7380 KB Output is correct
8 Correct 4 ms 7380 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 5 ms 7380 KB Output is correct
13 Correct 4 ms 7264 KB Output is correct
14 Correct 4 ms 7380 KB Output is correct
15 Correct 4 ms 7352 KB Output is correct
16 Correct 5 ms 7380 KB Output is correct
17 Correct 5 ms 7332 KB Output is correct
18 Correct 4 ms 7380 KB Output is correct
19 Correct 4 ms 7380 KB Output is correct
20 Correct 222 ms 22960 KB Output is correct
21 Correct 215 ms 23076 KB Output is correct
22 Correct 216 ms 23024 KB Output is correct
23 Correct 214 ms 23080 KB Output is correct
24 Correct 209 ms 23032 KB Output is correct
25 Correct 222 ms 23060 KB Output is correct
26 Correct 222 ms 22972 KB Output is correct
27 Correct 209 ms 23124 KB Output is correct
28 Correct 223 ms 23056 KB Output is correct
29 Correct 207 ms 22968 KB Output is correct
30 Correct 228 ms 22968 KB Output is correct
31 Correct 206 ms 23004 KB Output is correct
32 Correct 218 ms 23504 KB Output is correct
33 Correct 222 ms 22748 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 3 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 Correct 3 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 3 ms 7380 KB Output is correct
8 Correct 4 ms 7380 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 5 ms 7380 KB Output is correct
13 Correct 4 ms 7264 KB Output is correct
14 Correct 4 ms 7380 KB Output is correct
15 Correct 4 ms 7352 KB Output is correct
16 Correct 5 ms 7380 KB Output is correct
17 Correct 5 ms 7332 KB Output is correct
18 Correct 4 ms 7380 KB Output is correct
19 Correct 4 ms 7380 KB Output is correct
20 Correct 3900 ms 414904 KB Output is correct
21 Correct 2794 ms 414608 KB Output is correct
22 Correct 2950 ms 414600 KB Output is correct
23 Correct 3096 ms 414528 KB Output is correct
24 Correct 3606 ms 414624 KB Output is correct
25 Correct 4057 ms 414744 KB Output is correct
26 Correct 3917 ms 414884 KB Output is correct
27 Correct 3932 ms 414800 KB Output is correct
28 Correct 3854 ms 414624 KB Output is correct
29 Correct 3456 ms 409952 KB Output is correct
30 Correct 3971 ms 414732 KB Output is correct
31 Correct 3930 ms 414708 KB Output is correct
32 Correct 3989 ms 414700 KB Output is correct
33 Correct 3908 ms 414624 KB Output is correct
34 Correct 2580 ms 382640 KB Output is correct
35 Correct 3951 ms 414704 KB Output is correct
36 Correct 3920 ms 414608 KB Output is correct
37 Correct 2782 ms 414432 KB Output is correct
38 Correct 3011 ms 414368 KB Output is correct
39 Correct 3124 ms 414608 KB Output is correct
40 Correct 3532 ms 414580 KB Output is correct
41 Correct 4022 ms 414744 KB Output is correct
42 Correct 3828 ms 414808 KB Output is correct
43 Correct 3738 ms 414800 KB Output is correct
44 Correct 3709 ms 414816 KB Output is correct
45 Correct 3315 ms 409980 KB Output is correct
46 Correct 3811 ms 414792 KB Output is correct
47 Correct 3805 ms 414748 KB Output is correct
48 Correct 3852 ms 414700 KB Output is correct
49 Correct 3764 ms 414748 KB Output is correct
50 Correct 2484 ms 383028 KB Output is correct
51 Correct 3728 ms 414696 KB Output is correct

Subtask #6
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 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 Correct 3 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 3 ms 7380 KB Output is correct
8 Correct 4 ms 7380 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 5 ms 7380 KB Output is correct
13 Correct 4 ms 7264 KB Output is correct
14 Correct 4 ms 7380 KB Output is correct
15 Correct 4 ms 7352 KB Output is correct
16 Correct 5 ms 7380 KB Output is correct
17 Correct 5 ms 7332 KB Output is correct
18 Correct 4 ms 7380 KB Output is correct
19 Correct 4 ms 7380 KB Output is correct
20 Correct 3900 ms 414904 KB Output is correct
21 Correct 2794 ms 414608 KB Output is correct
22 Correct 2950 ms 414600 KB Output is correct
23 Correct 3096 ms 414528 KB Output is correct
24 Correct 3606 ms 414624 KB Output is correct
25 Correct 4057 ms 414744 KB Output is correct
26 Correct 3917 ms 414884 KB Output is correct
27 Correct 3932 ms 414800 KB Output is correct
28 Correct 3854 ms 414624 KB Output is correct
29 Correct 3456 ms 409952 KB Output is correct
30 Correct 3971 ms 414732 KB Output is correct
31 Correct 3930 ms 414708 KB Output is correct
32 Correct 3989 ms 414700 KB Output is correct
33 Correct 3908 ms 414624 KB Output is correct
34 Correct 2580 ms 382640 KB Output is correct
35 Correct 3951 ms 414704 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 Correct 3249 ms 426456 KB Output is correct
40 Correct 3255 ms 436228 KB Output is correct
41 Correct 3067 ms 436452 KB Output is correct
42 Correct 1949 ms 352192 KB Output is correct
43 Correct 1789 ms 315664 KB Output is correct
44 Correct 1726 ms 304656 KB Output is correct
45 Correct 3013 ms 436708 KB Output is correct
46 Correct 1799 ms 309788 KB Output is correct
47 Correct 4 ms 7380 KB Output is correct
48 Correct 222 ms 22960 KB Output is correct
49 Correct 215 ms 23076 KB Output is correct
50 Correct 216 ms 23024 KB Output is correct
51 Correct 214 ms 23080 KB Output is correct
52 Correct 209 ms 23032 KB Output is correct
53 Correct 222 ms 23060 KB Output is correct
54 Correct 222 ms 22972 KB Output is correct
55 Correct 209 ms 23124 KB Output is correct
56 Correct 223 ms 23056 KB Output is correct
57 Correct 207 ms 22968 KB Output is correct
58 Correct 228 ms 22968 KB Output is correct
59 Correct 206 ms 23004 KB Output is correct
60 Correct 218 ms 23504 KB Output is correct
61 Correct 222 ms 22748 KB Output is correct
62 Correct 3920 ms 414608 KB Output is correct
63 Correct 2782 ms 414432 KB Output is correct
64 Correct 3011 ms 414368 KB Output is correct
65 Correct 3124 ms 414608 KB Output is correct
66 Correct 3532 ms 414580 KB Output is correct
67 Correct 4022 ms 414744 KB Output is correct
68 Correct 3828 ms 414808 KB Output is correct
69 Correct 3738 ms 414800 KB Output is correct
70 Correct 3709 ms 414816 KB Output is correct
71 Correct 3315 ms 409980 KB Output is correct
72 Correct 3811 ms 414792 KB Output is correct
73 Correct 3805 ms 414748 KB Output is correct
74 Correct 3852 ms 414700 KB Output is correct
75 Correct 3764 ms 414748 KB Output is correct
76 Correct 2484 ms 383028 KB Output is correct
77 Correct 3728 ms 414696 KB Output is correct
78 Correct 3896 ms 424332 KB Output is correct
79 Correct 2870 ms 426248 KB Output is correct
80 Correct 3045 ms 425116 KB Output is correct
81 Correct 3244 ms 425204 KB Output is correct
82 Correct 3652 ms 424556 KB Output is correct
83 Correct 4103 ms 424316 KB Output is correct
84 Correct 3937 ms 424544 KB Output is correct
85 Correct 3895 ms 424524 KB Output is correct
86 Correct 3973 ms 424652 KB Output is correct
87 Correct 3515 ms 421640 KB Output is correct
88 Correct 3923 ms 424308 KB Output is correct
89 Correct 4041 ms 424368 KB Output is correct
90 Correct 3942 ms 424372 KB Output is correct
91 Correct 3950 ms 424324 KB Output is correct
92 Correct 2677 ms 395764 KB Output is correct
93 Correct 3917 ms 425384 KB Output is correct