oj.uz

Submission #554638

# Submission time Handle Problem Language Result Execution time Memory
554638 2022-04-29T02:48:37 Z amunduzbaev Reconstruction Project (JOI22_reconstruction) C++17
3 / 100
 5000 ms 18696 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){
			iota(p.begin(), p.end(), 0);
			sort(p.begin(), p.end(), [&](int i, int j){
				return abs(w[i] - x) < abs(w[j] - x);
			});
			
			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){
		return (w[i] > w[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;
		});
	}
	*/
	/*
	
	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){
		return (w[i] < w[j]);
	});
	
	for(int i=1;i<=n;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
 
*/

Compilation message

reconstruction.cpp: In lambda function:
reconstruction.cpp:77:8: warning: unused variable 'res' [-Wunused-variable]
   77 |    int res = 0;
      |        ^~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 2 ms 348 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 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 352 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 352 KB Output is correct
15 Correct 1 ms 348 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
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 2 ms 348 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 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 352 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 352 KB Output is correct
15 Correct 1 ms 348 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 Execution timed out 5046 ms 5060 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

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

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 2 ms 348 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 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 352 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 352 KB Output is correct
15 Correct 1 ms 348 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 2 ms 340 KB Output is correct
20 Correct 3378 ms 18464 KB Output is correct
21 Correct 3333 ms 17188 KB Output is correct
22 Correct 3386 ms 18500 KB Output is correct
23 Correct 3328 ms 18552 KB Output is correct
24 Correct 3331 ms 18696 KB Output is correct
25 Correct 3301 ms 18380 KB Output is correct
26 Incorrect 3371 ms 17680 KB Output isn't correct
27 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 2 ms 348 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 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 352 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 352 KB Output is correct
15 Correct 1 ms 348 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 Execution timed out 5046 ms 5060 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 2 ms 348 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 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 352 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 352 KB Output is correct
15 Correct 1 ms 348 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 Execution timed out 5046 ms 5060 KB Time limit exceeded
21 Halted 0 ms 0 KB -