Submission #734178

#	Time	Username	Problem	Language	Result	Execution time	Memory
734178		QwertyPi	Reconstruction Project (JOI22_reconstruction)	C++14	3 / 100	5013 ms	32012 KiB

reconstruction

#include <bits/stdc++.h>
#define int long long
using namespace std;

struct Edge{
	int u, v, w;
	bool operator< (const Edge& o) const {
		return w < o.w;
	}
};

const int N = 501, B = 500, M = 1e5 + 11;
vector<Edge> E, EM[M / B + 11], EL[M / B + 11], ER[M / B + 11];

struct DSU{
	int dsu[N];
	void in(){
		for(int i = 0; i < N; i++){
			dsu[i] = i;
		}
	}
	DSU(){
		in();
	}
	int f(int x){
		return x == dsu[x] ? x : dsu[x] = f(dsu[x]);
	}
	bool g(int x, int y){
		x = f(x), y = f(y);
		if(x == y) return false;
		dsu[x] = y;
		return true;
	}
};
int32_t main(){
	cin.tie(0); cout.tie(0)->sync_with_stdio(false);
	int n, m; cin >> n >> m;
	for(int i = 0; i < m; i++){
		int u, v, w; cin >> u >> v >> w; 
		E.push_back({u, v, w});
	}
	sort(E.begin(), E.end());
	for(int i = 0; i < (m + B - 1) / B; i++){
		int l = i * B, r = min(m, (i + 1) * B) - 1;
		vector<Edge> CE(E.begin() + l, E.begin() + r + 1), AL;
		EM[i] = CE;
		if(i != 0) for(auto j : EL[i - 1]) CE.push_back(j);
		sort(CE.begin(), CE.end());
		DSU dsu;
		for(auto e : CE){
			if(dsu.g(e.u, e.v)){
				AL.push_back(e);
			}
		}
		EL[i] = AL;
	}
	for(int i = (m + B - 1) / B - 1; i >= 0; i--){
		int l = i * B, r = min(m, (i + 1) * B) - 1;
		vector<Edge> CE(E.begin() + l, E.begin() + r + 1), AL;
		if(i != (m + B - 1) / B - 1) for(auto j : ER[i + 1]) CE.push_back(j);
		sort(CE.begin(), CE.end(), [](Edge x, Edge y){
			return y < x;
		});
		DSU dsu;
		for(auto e : CE){
			if(dsu.g(e.u, e.v)){
				AL.push_back(e);
			}
		}
		ER[i] = AL;
	}
	vector<int> Q;
	int q; cin >> q;
	for(int i = 0; i < q; i++){
		int v; cin >> v; Q.push_back(v);
	}
	for(int i = 0; i < q; i++){
		int v = Q[i]; int idx = lower_bound(E.begin(), E.end(), Edge{-1, -1, v}) - E.begin();
		int b = idx / B;
		vector<Edge> AL;
		if(b != 0) for(auto j : EL[b - 1]) AL.push_back(j);
		for(auto j : EM[b]) AL.push_back(j);
		for(auto j : ER[b + 1]) AL.push_back(j);
		for(auto& e : AL) e.w = abs(e.w - v);
		sort(AL.begin(), AL.end());
		int ans = 0;
		DSU dsu;
		for(auto& e : AL){
			if(dsu.g(e.u, e.v)){
				ans += e.w;
			}
		}
		cout << ans << endl;
	}
}

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