Submission #1125264

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125264		emptypringlescan	Reconstruction Project (JOI22_reconstruction)	C++17	100 / 100	763 ms	40128 KiB

reconstruction

#include <bits/stdc++.h>
using namespace std;
int n,m,q;
vector<pair<long long,pair<int,int> > > eds;
int par[505],sz[505];
int find(int x){
	if(par[x]==x) return x;
	return par[x]=find(par[x]);
}
void merge(int x, int y){
	x=find(x); y=find(y);
	if(x==y) return;
	if(sz[x]>sz[y]) swap(x,y);
	par[x]=y;
	sz[y]+=sz[x];
}
void res(){
	for(int i=0; i<=n; i++){
		par[i]=i;
		sz[i]=1;
	}
}
vector<pair<long long,pair<int,int> > > todo;
vector<int> good;
void rem(int x){
	for(int i=0; i<(int)good.size()-1; i++){
		if(good[i]==x) swap(good[i],good[i+1]);
	}
	assert(good.back()==x);
	good.pop_back();
}
int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;
	for(int i=0; i<m; i++){
		int a,b;
		long long w;
		cin >> a >> b >> w;
		eds.push_back({w,{a,b}});
	}
	sort(eds.begin(),eds.end());
	cin >> q;
	vector<pair<long long,int> > qu(q);
	long long ans[q];
	for(int i=0; i<q; i++){
		cin >> qu[i].first;
		qu[i].second=i;
	}
	sort(qu.begin(),qu.end());
	for(int i=0; i<m; i++){
		res();
		merge(eds[i].second.first,eds[i].second.second);
		int die=-1;
		for(int j=(int)good.size()-1; j>=0; j--){
			if(find(eds[good[j]].second.first)==find(eds[good[j]].second.second)){
				assert(die==-1);
				die=j;
			}
			merge(eds[good[j]].second.first,eds[good[j]].second.second);
		}
		if(die==-1) todo.push_back({0,{-1,i}});
		else{
			todo.push_back({(eds[good[die]].first+eds[i].first)/2,{good[die],i}});
			rem(good[die]);
		}
		good.push_back(i);
	}
	sort(todo.begin(),todo.end());
	long long cur=0,curx=0;
	long long l=0,r=0;
	priority_queue<long long,vector<long long>,greater<long long> > pq;
	int cq=0,ct=0;
	while(cq<q){
		long long smol=qu[cq].first;
		if(ct<(int)todo.size()) smol=min(smol,todo[ct].first);
		if(!pq.empty()) smol=min(smol,pq.top());
		cur+=(smol-curx)*(l-r);
		curx=smol;
		while(!pq.empty()&&pq.top()==smol){
			r--;
			l++;
			pq.pop();
		}
		while(cq<q&&qu[cq].first==smol){
			ans[qu[cq].second]=cur;
			cq++;
		}
		while(ct<(int)todo.size()&&todo[ct].first==smol){
			if(todo[ct].second.first!=-1){
				cur-=abs(curx-eds[todo[ct].second.first].first);
				l--;
			}
			cur+=abs(eds[todo[ct].second.second].first-curx);
			r++;
			pq.push(eds[todo[ct].second.second].first);
			ct++;
		}
	}
	for(int i=0; i<q; i++) cout << ans[i] << '\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