Submission #552486

#	Time	Username	Problem	Language	Result	Execution time	Memory
552486		kshitij_sodani	Reconstruction Project (JOI22_reconstruction)	C++14	31 / 100	5076 ms	26836 KiB

reconstruction

#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define a first
#define b second
#define pb push_back
const llo mod=1e9+7;
int n,m;
vector<pair<int,int>> adj[501];
vector<pair<int,pair<int,int>>> ee;
int ac=-1;
int cc=-1;
void dfs(int no,int par=-1,int ma=-1){
	if(ac==no){
		cc=ma;
	}
	for(auto j:adj[no]){
		if(j.a!=par){
			dfs(j.a,no,max(ma,j.b));
		}
	}
}
int re[100001];
void solve(){
	for(int i=0;i<n;i++){
		adj[i].clear();
	}
	for(int i=ee.size()-1;i>=0;i--){
		ac=ee[i].b.b;
		cc=-1;
		dfs(ee[i].b.a);
		if(cc==-1){
			adj[ac].pb({ee[i].b.a,i});
			adj[ee[i].b.a].pb({ac,i});
			re[i]=m;
		}
		else{
		//	cout<<22<<endl;
			vector<pair<int,int>> ee2;
			for(int j=0;j<n;j++){
				for(auto jj:adj[j]){
					if(jj.b==cc){
						continue;
					}
					ee2.pb(jj);
				}
				adj[j]=ee2;
				ee2.clear();
			}
			adj[ac].pb({ee[i].b.a,i});
			adj[ee[i].b.a].pb({ac,i});
			re[i]=cc;
		}

	}
}
llo vis[100001];
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	cin>>n>>m;
	
	for(int i=0;i<m;i++){
		int aa,bb,cc;
		cin>>aa>>bb>>cc;
		aa--;
		bb--;
		ee.pb({cc,{aa,bb}});
	}
	sort(ee.begin(),ee.end());
	solve();
	vector<pair<pair<int,int>,int>> qq;
	for(int i=0;i<m;i++){
		//if query>(x+y)/2
		if(re[i]<m){
			qq.pb({{(ee[i].a+ee[re[i]].a)/2,10},i});
		}
	}
	/*for(auto j:ee){
		cout<<j.a<<":"<<j.b.a<<":"<<j.b.b<<endl;
	}
	for(int i=0;i<ee.size();i++){
		cout<<re[i]<<",";
	}
	cout<<endl;*/
	//return 0;
	reverse(ee.begin(),ee.end());
	solve();
/*	for(int i=0;i<ee.size();i++){
		cout<<re[i]<<",";
	}
	cout<<endl;*/
	//return 0;
	for(int i=0;i<m;i++){
		//if query>(x+y)/2
		if(re[i]<m){
			qq.pb({{(ee[i].a+ee[re[i]].a+2)/2,-10},m-i-1});
		}
		else{
			qq.pb({{-10,-10},m-i-1});
		}
	}
	reverse(ee.begin(),ee.end());
	multiset<int> cur;
	int q;
	cin>>q;
	for(int ii=0;ii<q;ii++){
		int aa;
		cin>>aa;
		qq.pb({{aa,0},ii});
	}
	sort(qq.begin(),qq.end());
	for(auto j:qq){
		if(j.a.b==0){
			llo ans=0;
			for(auto jj:cur){
				ans+=abs(j.a.a-jj);
			}
			cout<<ans<<endl;
		}
		else if(j.a.b==-10){
			if(vis[j.b]==1){
				continue;
			}
			cur.insert(ee[j.b].a);
		}
		else if(j.a.b==10){

			auto jj=cur.find(ee[j.b].a);
			vis[j.b]=1;
			if(jj==cur.end()){
			//	cout<<-1<<endl;
				continue;
			}
			assert(jj!=cur.end());
			cur.erase(jj);
		}
	}



	return 0;
}

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