Submission #554292

#	Time	Username	Problem	Language	Result	Execution time	Memory
554292		Arvin	Reconstruction Project (JOI22_reconstruction)	C++11	7 / 100	5078 ms	8836 KiB

reconstruction

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int maxN = 505;

struct DSU {
	int parent[maxN], sz[maxN];
	
	void reset(){
		for(int x=0;x<maxN;x++){
			parent[x] = x;
			sz[x] = 1;
		}
	}
	
	int getParent(int x){
		if(parent[x] == x) return x;
		return parent[x] = getParent(parent[x]);
	}
	
	bool merge(int x, int y){
		int a = getParent(x);
		int b = getParent(y);
		
		if(a != b){
			if(sz[a] < sz[b]) swap(a, b);
			
			parent[b] = a;
			sz[a] += sz[b];
			return true;
		}
		return false;
	}
};

DSU dsu;

int main(){
	ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
	
	int n, m;
	cin >> n >> m;
	
	vector<array<ll, 3>> edge;
	for(int x=0;x<m;x++){
		ll a, b, w;
		cin >> a >> b >> w;
		
		a--; b--;
		edge.push_back({w, a, b});
	}
	
	sort(edge.begin(), edge.end());
	
	int q;
	cin >> q;
	
	int pos = -1;
	while(q--){
		ll val;
		cin >> val;
		
		while(pos+1 < m && edge[pos+1][0] <= val){
			pos++;
		}
		
		dsu.reset();
		int l = pos, r = pos+1;
		
		ll ans = 0;
		int cnt = n;
		while(cnt > 1){
			if(l >= 0 && r < m){
				if(val-edge[l][0] <= edge[r][0]-val){
					if(dsu.merge(edge[l][1], edge[l][2])){
						cnt--;
						ans += val-edge[l][0];
					}
					l--;
				} else {
					if(dsu.merge(edge[r][1], edge[r][2])){
						cnt--;
						ans += edge[r][0]-val;
					}
					r++;
				}
			} else if(l >= 0){
				if(dsu.merge(edge[l][1], edge[l][2])){
					cnt--;
					ans += val-edge[l][0];
				}
				l--;
			} else if(r < m){
				if(dsu.merge(edge[r][1], edge[r][2])){
					cnt--;
					ans += edge[r][0]-val;
				}
				r++;
			} else {
				assert(false);
			}
		}
		
		cout << ans << "\n";
	}
    return 0;
}

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