oj.uz

Submission #554471

# Submission time Handle Problem Language Result Execution time Memory
554471 2022-04-28T12:56:57 Z amunduzbaev Reconstruction Project (JOI22_reconstruction) C++17
3 / 100
 5000 ms 17644 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){
				if(merge(a[in], b[in])){
					if(in == i) return true;
				}
			} return 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 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 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 352 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 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
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 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 352 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 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 348 KB Output is correct
20 Execution timed out 5082 ms 4944 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 1 ms 340 KB Output is correct
4 Execution timed out 5079 ms 4868 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 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 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 352 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 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 3588 ms 17072 KB Output is correct
21 Correct 3610 ms 17644 KB Output is correct
22 Correct 3536 ms 16972 KB Output is correct
23 Correct 3618 ms 16460 KB Output is correct
24 Correct 3572 ms 16556 KB Output is correct
25 Correct 3564 ms 16660 KB Output is correct
26 Incorrect 3655 ms 15492 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 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 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 352 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 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 348 KB Output is correct
20 Execution timed out 5082 ms 4944 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 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 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 352 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 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 348 KB Output is correct
20 Execution timed out 5082 ms 4944 KB Time limit exceeded
21 Halted 0 ms 0 KB -