Submission #1313647

#	Time	Username	Problem	Language	Result	Execution time	Memory
1313647		vlomaczk	Reconstruction Project (JOI22_reconstruction)	C++20	100 / 100	1010 ms	81344 KiB

reconstruction

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
typedef long long ll;
using namespace __gnu_pbds;
using namespace std;

template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

ll M = 501;

struct Edge {
	ll a, b, c, i;

	friend bool operator<(Edge a, Edge b) {
		return a.c < b.c;
	}
};

vector<set<pair<ll, ll>>> g(M);
vector<ll> rep(M,1);
ll Find(ll v) {
	return (rep[v]==v ? v : rep[v] = Find(rep[v]));
}

bool Union(ll a, ll b) {
	if(Find(a)==Find(b)) return 0;
	rep[Find(a)]=rep[Find(b)];
	return 1;
}

vector<Edge> find_mst(vector<Edge> e) {
	vector<Edge> res;
	for(auto[a,b,w,i] : e) {
		if(Union(a,b)) {
			res.push_back({a,b,w,i});
		}
	}
	return res;
}

struct Moment {
	ll type; // 0-	answer query idx x, 1- swap edge x with y, 2- swap x from upper to lower
	ll pos; // position in time
	ll x,y;

	friend bool operator<(Moment a, Moment b) {
		if(a.pos!=b.pos) return a.pos < b.pos;
		return a.type > b.type;
	}
};

vector<Edge> e;
vector<ll> vis(M);
vector<ll> seen;

bool dfs(ll v, ll b) {
	if(vis[v]) return 0;
	vis[v] = 1;
	if(v==b) return 1;
	bool ans = 0;
	for(auto[u,i] : g[v]) {
		bool x = dfs(u,b);
		ans |= x;
		if(x) seen.push_back(i);
	}
	return ans;
}

Edge find_min(ll a, ll b) {
	for(ll i=1; i<M; ++i) vis[i] = 0;
	dfs(a,b);
	ll i=seen[0];
	for(auto x : seen) if(e[x].c < e[i].c) i=x;
	while(seen.size()) seen.pop_back();
	return e[i];
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	for(ll i=1; i<M; ++i) rep[i] = i;

	ll n, m;
	cin >> n >> m;
	e.resize(m);
	for(ll i=0; i<m; ++i) {
		cin >> e[i].a >> e[i].b >> e[i].c;
	}
	sort(e.begin(), e.end());
	ll idx = 0;
	for(auto &x : e) x.i = idx++;
	ll upper=n-1, lower=0;
	ll sum_upper=0, sum_lower=0;
	vector<Edge> mst = find_mst(e);
	set<ll> mst_set;
	for(auto x : mst) {
		sum_upper += x.c;
		g[x.a].insert({x.b,x.i});
		g[x.b].insert({x.a,x.i});
		mst_set.insert(x.i);
	}
	ll q; cin >> q;
	vector<ll> ans(q);
	vector<Moment> sweep;
	for(ll t=0; t<q; ++t) {
		ll x; cin >> x;
		sweep.push_back({0,x,t,0});
	}
	for(auto[a,b,w,i] : e) {
		Edge x = find_min(a,b);
		g[x.a].erase({x.b,x.i});
		g[x.b].erase({x.a,x.i});
		g[a].insert({b,i});
		g[b].insert({a,i});
		if(mst_set.find(i)==mst_set.end()) sweep.push_back({1,(w+x.c)/2 + 1, x.i, i});
		sweep.push_back({2, w, i, 0});
	}	
	sort(sweep.begin(), sweep.end());
	for(auto[type,pos,x,y] : sweep) {
		if(type==0) {
			ans[x] = lower*pos - sum_lower + sum_upper - upper * pos; 
		} else if(type==1) {
			lower--;
			upper++;
			sum_lower -= e[x].c;
			sum_upper += e[y].c;
			// cout << e[x].c << " -> " << e[y].c << "\n";
		} else {
			// cout << pos << "\n";
			upper--;
			lower++;
			sum_upper -= e[x].c;
			sum_lower += e[x].c;
		}
	}
	for(ll i=0; i<q; ++i) cout << ans[i] << "\n";

	return 0;
}

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