oj.uz

Submission #874152

# Submission time Handle Problem Language Result Execution time Memory
874152 2023-11-16T10:52:35 Z AmirAli_H1 Reconstruction Project (JOI22_reconstruction) C++17
100 / 100
 4578 ms 447512 KB 
// In the name of Allah
 
#include <bits/stdc++.h>
using namespace std;
 
typedef 	long long int			ll;
typedef 	long double				ld;
typedef 	pair<int, int>			pii;
typedef 	pair<ll, ll>			pll;
 
#define 	all(x)					(x).begin(),(x).end()
#define 	len(x)					((ll) (x).size())
#define 	F						first
#define 	S						second
#define 	pb						push_back
#define 	sep						' '
#define 	endl					'\n'
#define 	Mp						make_pair
#define 	kill(x)					cout << x << '\n', exit(0)
#define 	set_dec(x)				cout << fixed << setprecision(x);
#define 	file_io(x,y)			freopen(x, "r", stdin); freopen(y, "w", stdout);
 
int n, m, q;
const int maxn = 1e5 + 4;
const int maxm = 500 + 4;
const int maxs = 1e6 + 4;
const int oo = 1e9 + 3;
int p[maxn], sz[maxn]; pii ind[maxn];
int E1[maxn][maxm], s1[maxn];
int E2[maxn][maxm], s2[maxn];
vector<int> arr, arrx, Q, vc;
vector<pair<pii, int>> E;
pll res[maxs];
 
inline int GIx(int x) {
	return lower_bound(all(arrx), x) - arrx.begin();
}
 
int get(int a) {
	return (p[a] == a) ? a : p[a] = get(p[a]);
}
 
inline bool merge(int a, int b) {
	a = get(a); b = get(b);
	if (a == b) return 0;
	if (sz[a] > sz[b]) swap(a, b);
	p[a] = b; sz[b] += sz[a]; sz[a] = 0;
	return 1;
}
 
inline bool cmp(int r1, int r2, int x) {
	int w1 = abs(x - E[r1].S), w2 = abs(x - E[r2].S);
	return (Mp(w1, r1) < Mp(w2, r2));
}
 
inline bool cmpx(pair<pii, int> x, pair<pii, int> y) {
	return (x.S < y.S);
}
 
inline void add_val(int l, int r, pll x) {
	if (r <= l) return ;
	
	l = GIx(l); r = GIx(r);
	res[l].F += x.F; res[l].S += x.S;
	res[r].F -= x.F; res[r].S -= x.S;
}
 
inline void cal(int x, int j) {
	vc.clear();
	iota(p, p + n, 0); fill(sz, sz + n, 1);
	
	int p1 = 0, p2 = 0;
	while (p1 < s1[j - 1] && p2 < s2[j]) {
		int r1 = E1[j - 1][p1], r2 = E2[j][p2];
		if (cmp(r1, r2, x)) {
			if (merge(E[r1].F.F, E[r1].F.S)) vc.pb(r1);
			p1++;
		}
		else {
			if (merge(E[r2].F.F, E[r2].F.S)) vc.pb(r2);
			p2++;
		}
	}
	while (p1 < s1[j - 1]) {
		int r1 = E1[j - 1][p1];
		if (merge(E[r1].F.F, E[r1].F.S)) vc.pb(r1);
		p1++;
	}
	while (p2 < s2[j]) {
		int r2 = E2[j][p2];
		if (merge(E[r2].F.F, E[r2].F.S)) vc.pb(r2);
		p2++;
	}
}
 
inline void cal1(int ind, int i) {
	iota(p, p + n, 0); fill(sz, sz + n, 1);
	
	int ux = E[ind].F.F, vx = E[ind].F.S; int wx = E[ind].S;
	int j = find(E2[i], E2[i] + s2[i], ind) - E2[i];
	for (int r = 0; r < j; r++) {
		int x = E2[i][r];
		int u = E[x].F.F, v = E[x].F.S;
		merge(u, v);
	}
	for (int r = 0; r < s1[i - 1]; r++) {
		int x = E1[i - 1][r];
		int u = E[x].F.F, v = E[x].F.S;
		if ((get(u) == get(ux) && get(v) == get(vx)) || (get(u) == get(vx) && get(v) == get(ux))) {
			int w = E[x].S;
			int R = (w + wx) / 2;
			if (!cmp(ind, x, R)) R++;
			add_val(R, wx + 1, Mp(-1, wx));
			return ;
		}
		merge(u, v);
	}
	add_val(-oo, wx + 1, Mp(-1, wx));
}
 
inline void cal2(int ind, int i) {
	iota(p, p + n, 0); fill(sz, sz + n, 1);
	
	int ux = E[ind].F.F, vx = E[ind].F.S; int wx = E[ind].S;
	int j = find(E1[i], E1[i] + s1[i], ind) - E1[i];
	for (int r = 0; r < j; r++) {
		int x = E1[i][r];
		int u = E[x].F.F, v = E[x].F.S;
		merge(u, v);
	}
	for (int r = 0; r < s2[i + 1]; r++) {
		int x = E2[i + 1][r];
		int u = E[x].F.F, v = E[x].F.S;
		if ((get(u) == get(ux) && get(v) == get(vx)) || (get(u) == get(vx) && get(v) == get(ux))) {
			int w = E[x].S;
			int R = (w + wx) / 2;
			if (!cmp(ind, x, R)) R--;
			add_val(wx, R + 1, Mp(1, -wx));
			return ;
		}
		merge(u, v);
	}
	add_val(wx, oo, Mp(1, -wx));
}
 
int main() {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	
	arr.pb(-oo); arr.pb(oo);
	arrx.pb(-oo); arrx.pb(oo);
	
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int u, v, w;
		cin >> u >> v >> w; u--; v--;
		E.pb(Mp(Mp(u, v), w)); arr.pb(w);
	}
	sort(all(E), cmpx);
	cin >> q;
	for (int i = 0; i < q; i++) {
		int x; cin >> x;
		Q.pb(x); arrx.pb(x);
	}
	
	sort(all(arr)); arr.resize(unique(all(arr)) - arr.begin());
	sort(all(arrx)); arrx.resize(unique(all(arrx)) - arrx.begin());
	
	int j = 0;
	for (int i = 0; i < len(arr); i++) {
		iota(p, p + n, 0); fill(sz, sz + n, 1);
		while (j < m && arr[i] > E[j].S) j++;
		while (j < m && arr[i] == E[j].S) {
			int u = E[j].F.F, v = E[j].F.S;
			if (merge(u, v)) E1[i][s1[i]++] = j;
			j++;
		}
		if (i - 1 >= 0) {
			for (int r = 0; r < s1[i - 1]; r++) {
				int j = E1[i - 1][r];
				int u = E[j].F.F, v = E[j].F.S;
				if (merge(u, v)) E1[i][s1[i]++] = j;
			}
		}
	}
	
	j = m - 1;
	for (int i = len(arr) - 1; i >= 0; i--) {
		iota(p, p + n, 0); fill(sz, sz + n, 1);
		int j1 = j, j2 = j;
		while (j >= 0 && arr[i] < E[j].S) j--, j1--, j2--;
		while (j >= 0 && arr[i] == E[j].S) j--, j1--;
		
		for (int j = j1 + 1; j <= j2; j++) {
			int u = E[j].F.F, v = E[j].F.S;
			if (merge(u, v)) E2[i][s2[i]++] = j;
		}
		
		if (i + 1 < len(arr)) {
			for (int r = 0; r < s2[i + 1]; r++) {
				int j = E2[i + 1][r];
				int u = E[j].F.F, v = E[j].F.S;
				if (merge(u, v)) E2[i][s2[i]++] = j;
			}
		}
	}
	
	fill(ind, ind + m, Mp(oo, -oo));
	for (int i = 1; i < len(arr) - 1; i++) {
		cal(arr[i], i);
		for (int j : vc) {
			ind[j].F = min(ind[j].F, i);
			ind[j].S = max(ind[j].S, i);
		}
	}
	
	for (int i = 0; i < m; i++) {
		if (ind[i].F == oo) continue;
		
		int i1 = ind[i].F, i2 = ind[i].S;
		cal1(i, i1); cal2(i, i2);
	}
	
	for (int i = 1; i <= len(arrx); i++) {
		res[i].F += res[i - 1].F; res[i].S += res[i - 1].S;
	}
	for (int i = 0; i < q; i++) {
		ll x = Q[i]; int j = GIx(x);
		cout << res[j].F * x + res[j].S << endl;
	}
	
	return 0;
}

Subtask #1
3.0 / 3.0

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

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4564 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4440 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 1 ms 4444 KB Output is correct
12 Correct 1 ms 4444 KB Output is correct
13 Correct 1 ms 4440 KB Output is correct
14 Correct 1 ms 4444 KB Output is correct
15 Correct 1 ms 4444 KB Output is correct
16 Correct 1 ms 4440 KB Output is correct
17 Correct 1 ms 4440 KB Output is correct
18 Correct 1 ms 4440 KB Output is correct
19 Correct 1 ms 4444 KB Output is correct
20 Correct 4358 ms 399876 KB Output is correct
21 Correct 3111 ms 401064 KB Output is correct
22 Correct 3313 ms 401156 KB Output is correct
23 Correct 3690 ms 401092 KB Output is correct
24 Correct 4106 ms 400980 KB Output is correct
25 Correct 4192 ms 401004 KB Output is correct
26 Correct 4293 ms 401260 KB Output is correct
27 Correct 4248 ms 384440 KB Output is correct
28 Correct 1473 ms 12764 KB Output is correct
29 Correct 84 ms 8680 KB Output is correct
30 Correct 4340 ms 401236 KB Output is correct
31 Correct 4310 ms 400788 KB Output is correct
32 Correct 4329 ms 401056 KB Output is correct
33 Correct 4307 ms 401300 KB Output is correct
34 Correct 32 ms 8928 KB Output is correct
35 Correct 4329 ms 401048 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 4035 ms 440040 KB Output is correct
5 Correct 4018 ms 445424 KB Output is correct
6 Correct 4105 ms 445216 KB Output is correct
7 Correct 1679 ms 447248 KB Output is correct
8 Correct 1307 ms 447436 KB Output is correct
9 Correct 1233 ms 447264 KB Output is correct
10 Correct 3975 ms 445532 KB Output is correct
11 Correct 1322 ms 447512 KB Output is correct

Subtask #4
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4564 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4440 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 1 ms 4444 KB Output is correct
12 Correct 1 ms 4444 KB Output is correct
13 Correct 1 ms 4440 KB Output is correct
14 Correct 1 ms 4444 KB Output is correct
15 Correct 1 ms 4444 KB Output is correct
16 Correct 1 ms 4440 KB Output is correct
17 Correct 1 ms 4440 KB Output is correct
18 Correct 1 ms 4440 KB Output is correct
19 Correct 1 ms 4444 KB Output is correct
20 Correct 232 ms 49488 KB Output is correct
21 Correct 226 ms 49376 KB Output is correct
22 Correct 230 ms 49396 KB Output is correct
23 Correct 241 ms 49652 KB Output is correct
24 Correct 238 ms 49308 KB Output is correct
25 Correct 236 ms 49332 KB Output is correct
26 Correct 228 ms 47168 KB Output is correct
27 Correct 213 ms 45468 KB Output is correct
28 Correct 232 ms 52644 KB Output is correct
29 Correct 232 ms 52896 KB Output is correct
30 Correct 238 ms 52916 KB Output is correct
31 Correct 231 ms 52528 KB Output is correct
32 Correct 204 ms 49224 KB Output is correct
33 Correct 233 ms 53172 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4564 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4440 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 1 ms 4444 KB Output is correct
12 Correct 1 ms 4444 KB Output is correct
13 Correct 1 ms 4440 KB Output is correct
14 Correct 1 ms 4444 KB Output is correct
15 Correct 1 ms 4444 KB Output is correct
16 Correct 1 ms 4440 KB Output is correct
17 Correct 1 ms 4440 KB Output is correct
18 Correct 1 ms 4440 KB Output is correct
19 Correct 1 ms 4444 KB Output is correct
20 Correct 4358 ms 399876 KB Output is correct
21 Correct 3111 ms 401064 KB Output is correct
22 Correct 3313 ms 401156 KB Output is correct
23 Correct 3690 ms 401092 KB Output is correct
24 Correct 4106 ms 400980 KB Output is correct
25 Correct 4192 ms 401004 KB Output is correct
26 Correct 4293 ms 401260 KB Output is correct
27 Correct 4248 ms 384440 KB Output is correct
28 Correct 1473 ms 12764 KB Output is correct
29 Correct 84 ms 8680 KB Output is correct
30 Correct 4340 ms 401236 KB Output is correct
31 Correct 4310 ms 400788 KB Output is correct
32 Correct 4329 ms 401056 KB Output is correct
33 Correct 4307 ms 401300 KB Output is correct
34 Correct 32 ms 8928 KB Output is correct
35 Correct 4329 ms 401048 KB Output is correct
36 Correct 4376 ms 401576 KB Output is correct
37 Correct 3140 ms 402216 KB Output is correct
38 Correct 3290 ms 401904 KB Output is correct
39 Correct 3749 ms 401840 KB Output is correct
40 Correct 4094 ms 401944 KB Output is correct
41 Correct 4246 ms 401952 KB Output is correct
42 Correct 4315 ms 401956 KB Output is correct
43 Correct 4284 ms 385404 KB Output is correct
44 Correct 1467 ms 15580 KB Output is correct
45 Correct 78 ms 11484 KB Output is correct
46 Correct 4333 ms 401936 KB Output is correct
47 Correct 4321 ms 402108 KB Output is correct
48 Correct 4368 ms 401932 KB Output is correct
49 Correct 4326 ms 402136 KB Output is correct
50 Correct 31 ms 11488 KB Output is correct
51 Correct 4326 ms 401720 KB Output is correct

Subtask #6
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4564 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4440 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 1 ms 4444 KB Output is correct
12 Correct 1 ms 4444 KB Output is correct
13 Correct 1 ms 4440 KB Output is correct
14 Correct 1 ms 4444 KB Output is correct
15 Correct 1 ms 4444 KB Output is correct
16 Correct 1 ms 4440 KB Output is correct
17 Correct 1 ms 4440 KB Output is correct
18 Correct 1 ms 4440 KB Output is correct
19 Correct 1 ms 4444 KB Output is correct
20 Correct 4358 ms 399876 KB Output is correct
21 Correct 3111 ms 401064 KB Output is correct
22 Correct 3313 ms 401156 KB Output is correct
23 Correct 3690 ms 401092 KB Output is correct
24 Correct 4106 ms 400980 KB Output is correct
25 Correct 4192 ms 401004 KB Output is correct
26 Correct 4293 ms 401260 KB Output is correct
27 Correct 4248 ms 384440 KB Output is correct
28 Correct 1473 ms 12764 KB Output is correct
29 Correct 84 ms 8680 KB Output is correct
30 Correct 4340 ms 401236 KB Output is correct
31 Correct 4310 ms 400788 KB Output is correct
32 Correct 4329 ms 401056 KB Output is correct
33 Correct 4307 ms 401300 KB Output is correct
34 Correct 32 ms 8928 KB Output is correct
35 Correct 4329 ms 401048 KB Output is correct
36 Correct 1 ms 4440 KB Output is correct
37 Correct 1 ms 4444 KB Output is correct
38 Correct 1 ms 4444 KB Output is correct
39 Correct 4035 ms 440040 KB Output is correct
40 Correct 4018 ms 445424 KB Output is correct
41 Correct 4105 ms 445216 KB Output is correct
42 Correct 1679 ms 447248 KB Output is correct
43 Correct 1307 ms 447436 KB Output is correct
44 Correct 1233 ms 447264 KB Output is correct
45 Correct 3975 ms 445532 KB Output is correct
46 Correct 1322 ms 447512 KB Output is correct
47 Correct 1 ms 4444 KB Output is correct
48 Correct 232 ms 49488 KB Output is correct
49 Correct 226 ms 49376 KB Output is correct
50 Correct 230 ms 49396 KB Output is correct
51 Correct 241 ms 49652 KB Output is correct
52 Correct 238 ms 49308 KB Output is correct
53 Correct 236 ms 49332 KB Output is correct
54 Correct 228 ms 47168 KB Output is correct
55 Correct 213 ms 45468 KB Output is correct
56 Correct 232 ms 52644 KB Output is correct
57 Correct 232 ms 52896 KB Output is correct
58 Correct 238 ms 52916 KB Output is correct
59 Correct 231 ms 52528 KB Output is correct
60 Correct 204 ms 49224 KB Output is correct
61 Correct 233 ms 53172 KB Output is correct
62 Correct 4376 ms 401576 KB Output is correct
63 Correct 3140 ms 402216 KB Output is correct
64 Correct 3290 ms 401904 KB Output is correct
65 Correct 3749 ms 401840 KB Output is correct
66 Correct 4094 ms 401944 KB Output is correct
67 Correct 4246 ms 401952 KB Output is correct
68 Correct 4315 ms 401956 KB Output is correct
69 Correct 4284 ms 385404 KB Output is correct
70 Correct 1467 ms 15580 KB Output is correct
71 Correct 78 ms 11484 KB Output is correct
72 Correct 4333 ms 401936 KB Output is correct
73 Correct 4321 ms 402108 KB Output is correct
74 Correct 4368 ms 401932 KB Output is correct
75 Correct 4326 ms 402136 KB Output is correct
76 Correct 31 ms 11488 KB Output is correct
77 Correct 4326 ms 401720 KB Output is correct
78 Correct 4578 ms 444620 KB Output is correct
79 Correct 3351 ms 446312 KB Output is correct
80 Correct 3699 ms 444844 KB Output is correct
81 Correct 3992 ms 445632 KB Output is correct
82 Correct 4353 ms 444452 KB Output is correct
83 Correct 4453 ms 444520 KB Output is correct
84 Correct 4553 ms 444708 KB Output is correct
85 Correct 4485 ms 427832 KB Output is correct
86 Correct 1674 ms 56352 KB Output is correct
87 Correct 283 ms 53556 KB Output is correct
88 Correct 4567 ms 444684 KB Output is correct
89 Correct 4573 ms 444352 KB Output is correct
90 Correct 4570 ms 444236 KB Output is correct
91 Correct 4550 ms 444436 KB Output is correct
92 Correct 226 ms 54924 KB Output is correct
93 Correct 4550 ms 445308 KB Output is correct