oj.uz

Submission #554642

# Submission time Handle Problem Language Result Execution time Memory
554642 2022-04-29T02:59:59 Z amunduzbaev Reconstruction Project (JOI22_reconstruction) C++17
100 / 100
 2410 ms 248160 KB 
#include "bits/stdc++.h"
using namespace std;
 
#define ar array
#define int long long
const int N = 1e5 + 5;
const int M = 1e9 + 5;
const int MAXN = 505;
 
struct ST{
	long long tree[N * 60];
	int ch[N * 60][2], last;
	ST(){
		last = 0;
	}
	
	int bala(int x, int t){
		if(!ch[x][t]){
			ch[x][t] = ++last;
		}
		return ch[x][t];
	}
	
	void add(int l, int r, long long v, int lx = 0, int rx = M, int x = 0){
		if(lx > r || rx < l) return;
		if(lx >= l && rx <= r){
			tree[x] += v;
			return;
		} int m = (lx + rx) >> 1;
		add(l, r, v, lx, m, bala(x, 0));
		add(l, r, v, m+1, rx, bala(x, 1));
	}
	
	long long get(int i, int lx = 0, int rx = M, int x = 0){
		if(lx == rx) return tree[x];
		int m = (lx + rx) >> 1;
		if(i <= m && ch[x][0]) return tree[x] + get(i, lx, m, ch[x][0]);
		if(m < i && ch[x][1]) return tree[x] + get(i, m+1, rx, ch[x][1]);
		return tree[x];
	}
}tree, cnt;
 
int a[N], b[N], w[N];
vector<int> edges[MAXN];
 
signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n, m; cin>>n>>m;
	vector<int> p(m);
	for(int i=0;i<m;i++){ p[i] = i;
		cin>>a[i]>>b[i]>>w[i];
	}
	/*
	for(int i=0;i<m;i++){
		int l = w[i] - 1, r = M;
		
		auto check = [&](int x){
			vector<ar<int, 2>> P(m);
			for(int i=0;i<m;i++) P[i] = {abs(w[i] - x), i};
			sort(P.begin(), P.end());
			for(int i=0;i<m;i++) p[i] = P[i][1];
			
			vector<int> par(n + 1), sz(n + 1, 1);
			iota(par.begin(), par.end(), 0);
			function<int(int)> f = [&](int x){
				return (par[x] == x ? x : par[x] = f(par[x]));
			};
			auto merge = [&](int a, int b){
				a = f(a), b = f(b);
				if(a == b) return false;
				if(sz[a] < sz[b]) swap(a, b);
				sz[a] += sz[b], par[b] = a;
				return true;
			};
			
			int res = 0;
			for(auto in : p){
				bool is = merge(a[in], b[in]);
				if(in == i){
					return is;	
				}
			} assert(false);
		};
		
		while(l < r){
			int m = (l + r + 1) >> 1;
			if(check(m)) l = m;
			else r = m - 1;
		}
		
		int R = l;
		if(w[i] <= R){
			tree.add(w[i], R, -w[i]);
			cnt.add(w[i], R, 1);
		}
		
		l = 0, r = w[i] + 1;
		while(l < r){
			int m = (l + r) >> 1;
			if(check(m)) r = m;
			else l = m + 1;	
		}
		
		int L = l;
		if(L <= w[i]){
			tree.add(L, w[i], w[i]);
			cnt.add(L, w[i], -1);	
		}
		
		// cout<<L<<" "<<R<<"\n";
	} */
	
	/*
	sort(p.begin(), p.end(), [&](int i, int j){
		if(w[i] != w[j]) return (w[i] > w[j]);
		else return i < j;
	});
	
	vector<int> P;
	for(int l=0;l<(int)p.size();l++){
		int i = p[l];
		vector<int> par(n + 1), sz(n + 1, 1);
		iota(par.begin(), par.end(), 0);
		int in = -1, R = M;
		
		function<int(int)> f = [&](int x) { return (par[x] == x ? x : par[x] = f(par[x])); };
		auto merge = [&](int a, int b){
			a = f(a), b = f(b);
			if(a == b) return;
			if(sz[a] < sz[b]) swap(a, b);
			sz[a] += sz[b], par[b] = a;
		};
		
		for(auto x : P){
			merge(a[x], b[x]);
			if(f(a[i]) == f(b[i])){
				in = x;
				break;
			}
		}
		
		if(in == -1){
			R = M;
		} else {
		    R = (w[i] + w[in]) / 2;
			if((w[in]&1) == (w[i]&1) && in < i) R--;
		}
		
		if(w[i] <= R){
			tree.add(w[i], R, -w[i]);
			cnt.add(w[i], R, 1);
		}
		
		P.push_back(i);
		sort(P.begin(), P.end(), [&](int i, int j){
			if(w[i] != w[j]) return w[i] < w[j];
			else return i < j;
		});
	}
	
	sort(p.begin(), p.end(), [&](int i, int j){
		return (w[i] < w[j]);
	});
	P.clear();
	for(int l=0;l<(int)p.size();l++){
		int j = l - 1, i = p[l];
		vector<int> par(n + 1), sz(n + 1, 1);
		iota(par.begin(), par.end(), 0);
		int in = -1, L = 0;
		
		function<int(int)> f = [&](int x) { return (par[x] == x ? x : par[x] = f(par[x])); };
		auto merge = [&](int a, int b){
			a = f(a), b = f(b);
			if(a == b) return;
			if(sz[a] < sz[b]) swap(a, b);
			sz[a] += sz[b], par[b] = a;
		};
		
		for(auto x : P){
			merge(a[x], b[x]);
			if(f(a[i]) == f(b[i])){
				in = x;
				break;
			}
		}
		
		if(in == -1){
			L = 0;
		} else {
		    L = (w[i] + w[in] + 1) / 2;
			if((w[in]&1) == (w[i]&1) && in < i) L++;
		}
		
		if(L <= w[i]){
			tree.add(L, w[i], w[i]);
			cnt.add(L, w[i], -1);
		}
		
		P.push_back(i);
		sort(P.begin(), P.end(), [&](int i, int j){
			if(w[i] != w[j]) return w[i] > w[j];
			else return i < j;
		});
	}
	*/
	
	sort(p.begin(), p.end(), [&](int i, int j){
		if(w[i] != w[j]) return w[i] > w[j];
		else return i < j;
	});
	auto er = [&](vector<int>& a, int v){
		auto it = lower_bound(a.begin(), a.end(), v);
		a.erase(it);
	};
	
	w[m] = -1;
	for(auto i : p){
		int in = -1, R = w[i];
        function<void(int, int, int)> dfs = [&](int u, int ed, int p){
	        if(u == b[i]){
        		in = ed;
        		return;
        	}
        	
        	for(auto j : edges[u]){
        		int x = a[j] ^ b[j] ^ u;
        		if(x == p) continue;
        		int tmp = ed;
        		if(w[j] > w[ed]) tmp = j;
        		else if(w[j] == w[ed] && j > ed) tmp = j;
        		dfs(x, tmp, u);
        		if(~in) return;
        	}
	    };
	    
		dfs(a[i], m, a[i]);
		if(in == -1){
			R = M;
		} else {
		    R = (w[i] + w[in]) / 2;
			if((w[in]&1) == (w[i]&1) && in < i) R--;
			if(w[in] != w[i]){
				er(edges[a[in]], in);
				er(edges[b[in]], in);
			}
		}
		
		if(w[i] <= R){
			tree.add(w[i], R, -w[i]);
			cnt.add(w[i], R, 1);
		}
		if(w[in] != w[i]){
			edges[a[i]].push_back(i);
			sort(edges[a[i]].begin(), edges[a[i]].end());
			edges[b[i]].push_back(i);
			sort(edges[b[i]].begin(), edges[b[i]].end());
		}
	}
	
	sort(p.begin(), p.end(), [&](int i, int j){
		if(w[i] != w[j]) return w[i] < w[j];
		else return i < j;
	});
	
	for(int i=0;i<MAXN;i++) edges[i].clear();
	w[m] = M;
	for(auto i : p){
		int in = -1, L = w[i];
        function<void(int, int, int)> dfs = [&](int u, int ed, int p){
	        if(u == b[i]){
        		in = ed;
        		return;
        	}
        	
        	for(auto j : edges[u]){
        		int x = a[j] ^ b[j] ^ u;
        		if(x == p) continue;
        		int tmp = ed;
        		if(w[j] < w[ed]) tmp = j;
        		else if(w[j] == w[ed] && j > ed) tmp = j;
        		dfs(x, tmp, u);
        		if(~in) return;
        	}
	    };
	    
		dfs(a[i], m, a[i]);
		assert(in != m);
		if(in == -1){
			L = 0;
		} else {
		    L = (w[i] + w[in] + 1) / 2;
			if((w[in]&1) == (w[i]&1) && in < i) L++;
			if(w[in] != w[i]){
				er(edges[a[in]], in);
				er(edges[b[in]], in);
			}
		}
		
		if(L <= w[i]){
			tree.add(L, w[i], w[i]);
			cnt.add(L, w[i], -1);
		}
		if(w[in] != w[i]){
			edges[a[i]].push_back(i);
			sort(edges[a[i]].begin(), edges[a[i]].end());
			edges[b[i]].push_back(i);
			sort(edges[b[i]].begin(), edges[b[i]].end());
		}
	}
	
	int q; cin>>q;
	while(q--){
	    long long x; cin>>x;
	    cout<<tree.get(x) + cnt.get(x) * x<<"\n";
	}
}
 
/*
 
2 4 15
1 3 13
1 5 11
1 2 8
2 3 7
3 4 6
3 5 6
1 4 5
1 5 3
4 5 2
 
5 10
1 2 8
1 3 13
1 4 5
1 5 11
1 5 3
2 3 7
2 4 15
3 4 6
3 5 6
4 5 2
2
6
3
 
*/

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 280 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 348 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 348 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 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 280 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 348 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 348 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 2082 ms 227264 KB Output is correct
21 Correct 1002 ms 227080 KB Output is correct
22 Correct 1312 ms 227032 KB Output is correct
23 Correct 1402 ms 227036 KB Output is correct
24 Correct 1639 ms 227068 KB Output is correct
25 Correct 1988 ms 227040 KB Output is correct
26 Correct 2005 ms 228888 KB Output is correct
27 Correct 2051 ms 221272 KB Output is correct
28 Correct 1770 ms 8912 KB Output is correct
29 Correct 1080 ms 5196 KB Output is correct
30 Correct 2008 ms 228880 KB Output is correct
31 Correct 2037 ms 228900 KB Output is correct
32 Correct 1996 ms 228808 KB Output is correct
33 Correct 2013 ms 227260 KB Output is correct
34 Correct 857 ms 5320 KB Output is correct
35 Correct 2009 ms 228988 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 348 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1599 ms 240996 KB Output is correct
5 Correct 1549 ms 241696 KB Output is correct
6 Correct 1542 ms 241316 KB Output is correct
7 Correct 869 ms 242880 KB Output is correct
8 Correct 841 ms 243540 KB Output is correct
9 Correct 807 ms 243104 KB Output is correct
10 Correct 1415 ms 241136 KB Output is correct
11 Correct 706 ms 243064 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 280 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 348 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 348 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 272 ms 16856 KB Output is correct
21 Correct 253 ms 16696 KB Output is correct
22 Correct 277 ms 16876 KB Output is correct
23 Correct 272 ms 16924 KB Output is correct
24 Correct 264 ms 16844 KB Output is correct
25 Correct 286 ms 16900 KB Output is correct
26 Correct 261 ms 15980 KB Output is correct
27 Correct 225 ms 14376 KB Output is correct
28 Correct 266 ms 16516 KB Output is correct
29 Correct 257 ms 16588 KB Output is correct
30 Correct 249 ms 16460 KB Output is correct
31 Correct 254 ms 16204 KB Output is correct
32 Correct 202 ms 14200 KB Output is correct
33 Correct 253 ms 16360 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 280 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 348 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 348 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 2082 ms 227264 KB Output is correct
21 Correct 1002 ms 227080 KB Output is correct
22 Correct 1312 ms 227032 KB Output is correct
23 Correct 1402 ms 227036 KB Output is correct
24 Correct 1639 ms 227068 KB Output is correct
25 Correct 1988 ms 227040 KB Output is correct
26 Correct 2005 ms 228888 KB Output is correct
27 Correct 2051 ms 221272 KB Output is correct
28 Correct 1770 ms 8912 KB Output is correct
29 Correct 1080 ms 5196 KB Output is correct
30 Correct 2008 ms 228880 KB Output is correct
31 Correct 2037 ms 228900 KB Output is correct
32 Correct 1996 ms 228808 KB Output is correct
33 Correct 2013 ms 227260 KB Output is correct
34 Correct 857 ms 5320 KB Output is correct
35 Correct 2009 ms 228988 KB Output is correct
36 Correct 2045 ms 229324 KB Output is correct
37 Correct 1039 ms 229208 KB Output is correct
38 Correct 1339 ms 227300 KB Output is correct
39 Correct 1429 ms 227368 KB Output is correct
40 Correct 1596 ms 227528 KB Output is correct
41 Correct 1968 ms 227728 KB Output is correct
42 Correct 2009 ms 228504 KB Output is correct
43 Correct 2017 ms 221132 KB Output is correct
44 Correct 1770 ms 9420 KB Output is correct
45 Correct 1043 ms 5504 KB Output is correct
46 Correct 2037 ms 229104 KB Output is correct
47 Correct 2047 ms 229356 KB Output is correct
48 Correct 2025 ms 228796 KB Output is correct
49 Correct 2037 ms 227568 KB Output is correct
50 Correct 835 ms 3780 KB Output is correct
51 Correct 2011 ms 227548 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 280 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 348 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 348 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 2082 ms 227264 KB Output is correct
21 Correct 1002 ms 227080 KB Output is correct
22 Correct 1312 ms 227032 KB Output is correct
23 Correct 1402 ms 227036 KB Output is correct
24 Correct 1639 ms 227068 KB Output is correct
25 Correct 1988 ms 227040 KB Output is correct
26 Correct 2005 ms 228888 KB Output is correct
27 Correct 2051 ms 221272 KB Output is correct
28 Correct 1770 ms 8912 KB Output is correct
29 Correct 1080 ms 5196 KB Output is correct
30 Correct 2008 ms 228880 KB Output is correct
31 Correct 2037 ms 228900 KB Output is correct
32 Correct 1996 ms 228808 KB Output is correct
33 Correct 2013 ms 227260 KB Output is correct
34 Correct 857 ms 5320 KB Output is correct
35 Correct 2009 ms 228988 KB Output is correct
36 Correct 1 ms 340 KB Output is correct
37 Correct 1 ms 348 KB Output is correct
38 Correct 1 ms 340 KB Output is correct
39 Correct 1599 ms 240996 KB Output is correct
40 Correct 1549 ms 241696 KB Output is correct
41 Correct 1542 ms 241316 KB Output is correct
42 Correct 869 ms 242880 KB Output is correct
43 Correct 841 ms 243540 KB Output is correct
44 Correct 807 ms 243104 KB Output is correct
45 Correct 1415 ms 241136 KB Output is correct
46 Correct 706 ms 243064 KB Output is correct
47 Correct 1 ms 340 KB Output is correct
48 Correct 272 ms 16856 KB Output is correct
49 Correct 253 ms 16696 KB Output is correct
50 Correct 277 ms 16876 KB Output is correct
51 Correct 272 ms 16924 KB Output is correct
52 Correct 264 ms 16844 KB Output is correct
53 Correct 286 ms 16900 KB Output is correct
54 Correct 261 ms 15980 KB Output is correct
55 Correct 225 ms 14376 KB Output is correct
56 Correct 266 ms 16516 KB Output is correct
57 Correct 257 ms 16588 KB Output is correct
58 Correct 249 ms 16460 KB Output is correct
59 Correct 254 ms 16204 KB Output is correct
60 Correct 202 ms 14200 KB Output is correct
61 Correct 253 ms 16360 KB Output is correct
62 Correct 2045 ms 229324 KB Output is correct
63 Correct 1039 ms 229208 KB Output is correct
64 Correct 1339 ms 227300 KB Output is correct
65 Correct 1429 ms 227368 KB Output is correct
66 Correct 1596 ms 227528 KB Output is correct
67 Correct 1968 ms 227728 KB Output is correct
68 Correct 2009 ms 228504 KB Output is correct
69 Correct 2017 ms 221132 KB Output is correct
70 Correct 1770 ms 9420 KB Output is correct
71 Correct 1043 ms 5504 KB Output is correct
72 Correct 2037 ms 229104 KB Output is correct
73 Correct 2047 ms 229356 KB Output is correct
74 Correct 2025 ms 228796 KB Output is correct
75 Correct 2037 ms 227568 KB Output is correct
76 Correct 835 ms 3780 KB Output is correct
77 Correct 2011 ms 227548 KB Output is correct
78 Correct 2382 ms 240504 KB Output is correct
79 Correct 1344 ms 248160 KB Output is correct
80 Correct 1663 ms 247816 KB Output is correct
81 Correct 1779 ms 248052 KB Output is correct
82 Correct 2017 ms 247096 KB Output is correct
83 Correct 2400 ms 246876 KB Output is correct
84 Correct 2410 ms 245400 KB Output is correct
85 Correct 2377 ms 239416 KB Output is correct
86 Correct 1990 ms 17304 KB Output is correct
87 Correct 1207 ms 19404 KB Output is correct
88 Correct 2374 ms 247388 KB Output is correct
89 Correct 2356 ms 247500 KB Output is correct
90 Correct 2344 ms 239776 KB Output is correct
91 Correct 2289 ms 237312 KB Output is correct
92 Correct 1010 ms 16364 KB Output is correct
93 Correct 2260 ms 238372 KB Output is correct