Submission #1023173

#	Time	Username	Problem	Language	Result	Execution time	Memory
1023173		Unforgettablepl	Reconstruction Project (JOI22_reconstruction)	C++17	100 / 100	576 ms	30996 KiB

reconstruction

#pragma GCC optimize("Ofast","unroll-loops")
#include <bits/stdc++.h>
using namespace std;

// #define int long long


int32_t main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int n,m;
	cin >> n >> m;
	vector<pair<int,pair<int,int>>> edges(m);
	for(auto&[a,b]:edges)cin>>b.first>>b.second>>a;
	sort(edges.begin(),edges.end());
	vector<set<pair<int,int>>> adj(n+1);
	// Calculation from the front
	int tar;
	function<pair<bool,int>(int,int)> dfs = [&](int x,int p){
		if(x==tar)return make_pair(true,(int)1e15);
		for(auto[v,i]:adj[x])if(v!=p){
			auto res = dfs(v,x);
			if(res.first)return make_pair(true,min(res.second,i));
		}
		return make_pair(false,(int)0);
	};
	vector<tuple<int,bool,int>> events;
	for(int i=0;i<m;i++){
		tar = edges[i].second.second;
		auto res = dfs(edges[i].second.first,-1);
		if(res.first){
			//res.second is the edge which is replaced by i
			int diffpoint = (edges[i].first+edges[res.second].first+1)/2;
			events.emplace_back(diffpoint,true,+edges[i].first);
			events.emplace_back(diffpoint,false,-edges[res.second].first);
			adj[edges[res.second].second.first].erase({edges[res.second].second.second,res.second});
			adj[edges[res.second].second.second].erase({edges[res.second].second.first,res.second});
		} else {
			events.emplace_back(0,true,+edges[i].first);
		}
		events.emplace_back(edges[i].first,true,-edges[i].first);
		events.emplace_back(edges[i].first,false,+edges[i].first);
		adj[edges[i].second.first].insert({edges[i].second.second,i});
		adj[edges[i].second.second].insert({edges[i].second.first,i});
	}
	events.emplace_back(2e9,false,0);
	sort(events.begin(),events.end());
	long long smallersum = 0;
	long long biggersum = 0;
	long long smallercnt = 0;
	long long biggercnt = 0;
	auto iter = events.begin();
	int q;
	cin >> q;
	for(int i=1;i<=q;i++){
		long long query;
		cin >> query;
		while(get<0>(*iter)<=query){
			auto [a,b,c] = *iter;
			if(b){
				biggersum+=c;
				if(c<0)biggercnt--;
				else biggercnt++;
			} else {
				smallersum+=c;
				if(c<0)smallercnt--;
				else smallercnt++;
			}
			iter++;
		}
		cout << biggersum-query*biggercnt+query*smallercnt-smallersum << '\n';
	}
}

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