Submission #552494

#	Time	Username	Problem	Language	Result	Execution time	Memory
552494		kshitij_sodani	Reconstruction Project (JOI22_reconstruction)	C++14	100 / 100	4216 ms	63320 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;
llo n,m;
vector<pair<llo,llo>> adj[501];
vector<pair<llo,pair<llo,llo>>> ee;
llo ac=-1;
llo cc=-1;
void dfs(llo no,llo par=-1,llo ma=-1){
	if(ac==no){
		cc=ma;
	}
	for(auto j:adj[no]){
		if(j.a!=par){
			dfs(j.a,no,max(ma,j.b));
		}
	}
}
llo re[100001];
void solve(){
	for(llo i=0;i<n;i++){
		adj[i].clear();
	}
	for(llo 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<llo,llo>> ee2;
			for(llo 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];
pair<llo,llo> tree[4*100001];
void update(llo no,llo l,llo r,llo i,pair<llo,llo> j){
	if(l==r){
		tree[no]=j;
	}
	else{
		llo mid=(l+r)/2;
		if(i<=mid){
			update(no*2+1,l,mid,i,j);
		}
		else{
			update(no*2+2,mid+1,r,i,j);
		}
		tree[no].a=tree[no*2+1].a+tree[no*2+2].a;
		tree[no].b=tree[no*2+1].b+tree[no*2+2].b;
	}
}
pair<llo,llo> query(llo no,llo l,llo r,llo aa,llo bb){
	if(aa>bb or l>bb or r<aa){
		return {0,0};
	}
	if(aa<=l and r<=bb){
		return tree[no];
	}
	llo mid=(l+r)/2;
	pair<llo,llo> x=query(no*2+1,l,mid,aa,bb);
	pair<llo,llo> y=query(no*2+2,mid+1,r,aa,bb);
	return {x.a+y.a,x.b+y.b};
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	cin>>n>>m;
	
	for(llo i=0;i<m;i++){
		llo aa,bb,cc;
		cin>>aa>>bb>>cc;
		aa--;
		bb--;
		ee.pb({cc,{aa,bb}});
	}
	sort(ee.begin(),ee.end());
	solve();
	vector<pair<pair<llo,llo>,llo>> qq;
	for(llo 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(llo i=0;i<ee.size();i++){
		cout<<re[i]<<",";
	}
	cout<<endl;*/
	//return 0;
	reverse(ee.begin(),ee.end());
	solve();
/*	for(llo i=0;i<ee.size();i++){
		cout<<re[i]<<",";
	}
	cout<<endl;*/
	//return 0;
	for(llo 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<llo> cur;
	llo q;
	cin>>q;
	for(llo ii=0;ii<q;ii++){
		llo aa;
		cin>>aa;
		qq.pb({{aa,0},ii});
	}
	sort(qq.begin(),qq.end());
	for(llo i=0;i<4*m;i++){
		tree[i]={0,0};
	}
	for(auto j:qq){
		if(j.a.b==0){
			//llo ans=0;
			/*for(auto jj:cur){
				ans+=abs(j.a.a-jj);
			}*/
		
			llo low=-1;
			for(llo i=19;i>=0;i--){
				if(low+(1<<i)<m){
					if(ee[low+(1<<i)].a<=j.a.a){
						low+=(1<<i);
					}
				}
			}
			pair<llo,llo> x=query(0,0,m-1,0,low);
			
			pair<llo,llo> y=query(0,0,m-1,low+1,m-1);
		
			llo ans=j.a.a*x.a-x.b;
			ans+=(y.b-y.a*j.a.a);
			cout<<ans<<endl;
		}
		else if(j.a.b==-10){
			if(vis[j.b]==1){
				continue;
			}
			update(0,0,m-1,j.b,{1,ee[j.b].a});
			//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());
			update(0,0,m-1,j.b,{0,0});
			//cur.erase(jj);
		}
	}



	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