Submission #554490

#	Time	Username	Problem	Language	Result	Execution time	Memory
554490		amunduzbaev	Reconstruction Project (JOI22_reconstruction)	C++17	3 / 100	5044 ms	14984 KiB

reconstruction

#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, int 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];
	}
};

// ST 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];
	}
	
	vector<ar<int, 2>> tot, cnt;
	
	for(int i=0;i<m;i++){
		auto check = [&](int x){
			vector<int> p(m); 
			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]) && in == i) return true;
			} return false;
		};
		
		int l = w[i] - 1, r = M;
		while(l < r){
			int m = (l + r + 1) >> 1;
			if(check(m)) l = m;
			else r = m - 1;
		}
		
		if(w[i] <= r){
			tot.push_back({w[i], -w[i]});
			tot.push_back({r+1, w[i]});
			cnt.push_back({w[i], 1});
			cnt.push_back({r+1, -1});
			/* 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;	
		}
		
		if(l <= w[i]){
			tot.push_back({l, w[i]});
			tot.push_back({w[i]+1, -w[i]});
			cnt.push_back({l, -1});
			cnt.push_back({w[i]+1, 1});
			/* 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());
		}
	}
	*/
	
	sort(tot.begin(), tot.end());
	sort(cnt.begin(), cnt.end());
	for(int i=1;i<(int)tot.size();i++){
		tot[i][1] += tot[i-1][1];
		cnt[i][1] += cnt[i-1][1];
	}
	
	const int inf = 1e18;
	
	int q; cin>>q;
	while(q--){
	    int x; cin>>x;
	    long long res = 0;
		{
		    auto it = upper_bound(tot.begin(), tot.end(), (ar<int, 2>){x + 1, -inf});
		    if(it != tot.begin()){ it--;
			    res += (*it)[1];
			}
		}
		
		{
		    auto it = upper_bound(cnt.begin(), cnt.end(), (ar<int, 2>){x + 1, -inf});
		    if(it != cnt.begin()){ it--;
			    res += (*it)[1] * x;
			}
		}
		cout<<res<<"\n";
	    // 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 (stderr)

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

• Subtask 1: 3 / 3
• Subtask 2: 0 / 4
• Subtask 3: 0 / 7
• Subtask 4: 0 / 28
• Subtask 5: 0 / 35
• Subtask 6: 0 / 23