Submission #772477

#	Time	Username	Problem	Language	Result	Execution time	Memory
772477		minhcool	Reconstruction Project (JOI22_reconstruction)	C++17	35 / 100	3634 ms	79908 KiB

reconstruction

#define local
#ifndef local
#include ""
#endif
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;

#define int long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair

typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;

const int N = 2e6 + 5;

const int oo = 1e18 + 7, mod = 1e9 + 7;

mt19937 rng(1);

int rnd(int l, int r){
	int temp = rng() % (r - l + 1);
	return abs(temp) + l;
}

int n, m;

int le[N], ri[N];

vector<iii> edge;

vector<int> diffs;

bool cmp(iii a, iii b){
	return a.se < b.se;
}

vector<iii> cur_mst;

int rt[N], sz[N];

int root(int x){
	return (x == rt[x] ? x : rt[x] = root(rt[x]));
}

bool merge(int x, int y){
	x = root(x), y = root(y);
	if(x == y) return 0;
	if(sz[x] < sz[y]) swap(x, y);
	sz[x] += sz[y];
	rt[y] = x;
	return 1;
}

vector<ii> updates[N];

#ifdef local
void process(){
	cin >> n >> m;
	for(int i = 1; i <= m; i++){
		int x, y, w;
		cin >> x >> y >> w;
		edge.pb({{x, y}, w});
	}
	sort(edge.begin(), edge.end(), cmp);
	for(int i = 0; i < m; i++) le[i] = ri[i] = -oo;
	for(int i = 1; i < edge.size(); i++){
		cur_mst.pb({edge[i - 1].fi, i - 1});
		iii it = edge[i];
		for(int j = 1; j <= n; j++){
			rt[j] = j, sz[j] = 1;
		}
		vector<iii> nw;
		for(int j = cur_mst.size() - 1; j >= 0; j--){
			if(merge(cur_mst[j].fi.fi, cur_mst[j].fi.se)){
				nw.pb(cur_mst[j]);
				if(root(it.fi.fi) == root(it.fi.se) && le[i] < 0) le[i] = cur_mst[j].se;
			}
		}
		reverse(nw.begin(), nw.end());
		cur_mst = nw;
	}
	cur_mst.clear();
	for(int i = (int)edge.size() - 2; i >= 0; i--){
		cur_mst.pb({edge[i + 1].fi, i + 1});
		iii it = edge[i];
		for(int j = 1; j <= n; j++){
			rt[j] = j, sz[j] = 1;
		}
		vector<iii> nw;
		for(int j = cur_mst.size() - 1; j >= 0; j--){
			if(merge(cur_mst[j].fi.fi, cur_mst[j].fi.se)){
				nw.pb(cur_mst[j]);
				if(root(it.fi.fi) == root(it.fi.se) && ri[i] < 0) ri[i] = cur_mst[j].se;
			}
		}
		reverse(nw.begin(), nw.end());
		cur_mst = nw;
	//	cout << "OK " << i << "\n";
	//	for(auto it : cur_mst) cout << it.fi.fi << " " << it.fi.se << " " << it.se << "\n";
	}
	for(int i = 0; i < m; i++){
		int temp1 = (le[i] < 0 ? 0 : (edge[le[i]].se + edge[i].se + 2) / 2);
		int temp2 = (ri[i] < 0 ? 2e9 : (edge[i].se + edge[ri[i]].se) / 2);
	//	cout << i << " " << le[i] << " " << ri[i] << " " << temp1 << " " << temp2 << "\n";
		diffs.pb(temp1);
		diffs.pb(temp2 + 1);
	}
	sort(diffs.begin(), diffs.end());
	diffs.resize(unique(diffs.begin(), diffs.end()) - diffs.begin());
	for(int i = 0; i < m; i++){
		int temp1 = (le[i] < 0 ? 0 : (edge[le[i]].se + edge[i].se + 2) / 2);
		int temp2 = (ri[i] < 0 ? 2e9 : (edge[i].se + edge[ri[i]].se) / 2);
		int pos1 = lower_bound(diffs.begin(), diffs.end(), temp1) - diffs.begin();
		int pos2 = lower_bound(diffs.begin(), diffs.end(), temp2) - diffs.begin();
		updates[pos1].pb({i, 1});
		updates[pos2].pb({i, -1});
		//diffs.pb(temp1);
		//diffs.pb(temp2 + 1);	
	}
	multiset<int> mls;
	int q;
	cin >> q;
	int itr = 0;
	while(q--){
		int x;
		cin >> x;
		while(itr < diffs.size() && diffs[itr] <= x){
			for(auto it : updates[itr]){
		//		cout << edge[it.fi].se << " " << it.se << "\n";
				if(it.se > 0) mls.insert(edge[it.fi].se);
				else mls.erase(mls.find(edge[it.fi].se));
			} 
			itr++;
		}
		int total = 0, mx = 0;
		//for(auto it : mls) cout << it << " ";
	//	cout << "\n";
		for(auto it : mls){
			total += abs(it - x);
			mx = max(mx, it - x);
		}
		if(mls.size() != (n - 1)) total += (n - 1 - mls.size()) * mx;
		cout << total << "\n";
	}
	//for(int i = 0; i < 
}

signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	process();
}
#endif

Compilation message (stderr)

reconstruction.cpp: In function 'void process()':
reconstruction.cpp:72:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<std::pair<long long int, long long int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |  for(int i = 1; i < edge.size(); i++){
      |                 ~~^~~~~~~~~~~~~
reconstruction.cpp:133:13: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  133 |   while(itr < diffs.size() && diffs[itr] <= x){
      |         ~~~~^~~~~~~~~~~~~~
reconstruction.cpp:148:17: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
  148 |   if(mls.size() != (n - 1)) total += (n - 1 - mls.size()) * mx;
      |      ~~~~~~~~~~~^~~~~~~~~~

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