Submission #568866

#	Time	Username	Problem	Language	Result	Execution time	Memory
568866		errorgorn	Reconstruction Project (JOI22_reconstruction)	C++17	70 / 100	3401 ms	790256 KiB

reconstruction

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ii pair<int,int>
#define fi first
#define se second
#define endl '\n'

#define puf push_front
#define pof pop_front
#define pub push_back
#define pob pop_back
#define lb lower_bound
#define ub upper_bound

#define rep(x,s,e) for (int x=(s)-((s)>(e));x!=(e)-((s)>(e));((s)<(e))?x++:x--)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

struct UFDS{
	int p[505];
	int s[505];
	vector<ii> roll;
	
	UFDS(){
		rep(x,0,505) p[x]=x,s[x]=1;
		roll.clear();
	}
	
	int par(int i){
		while (p[i]!=i) i=p[i];
		return i;
	}
	
	bool unions(int i,int j){
		i=par(i),j=par(j);
		if (i==j) return false;
		
		if (s[i]>s[j]) swap(i,j);
		p[i]=j;
		s[j]+=s[i];
		roll.pub({i,j});
		
		return true;
	}
	
	void rollback(int ss){
		while (sz(roll)>ss){
			int i,j;
			tie(i,j)=roll.back(); roll.pob();
			
			p[i]=i;
			s[j]-=s[i];
		}
	}
} ufds;

struct UFDS2{
	int p[505];
	
	void reset(){
		rep(x,0,505) p[x]=x;
	}
	
	int par(int i){
		if (p[i]==i) return i;
		else return p[i]=par(p[i]);
	}
	
	bool unions(int i,int j){
		i=par(i),j=par(j);
		if (i==j) return false;
		p[i]=j;
		return true;
	}
} ufds2;

int n,m,q;
struct E{
	int u,v;
	int w;
};

E ee[100005];

void fix(vector<int> &v){
	vector<int> temp;
	
	ufds2.reset();
	while (!v.empty()){
		if (ufds2.unions(ee[v.back()].u,ee[v.back()].v)){
			temp.pub(v.back());
		}
		v.pob();
	}
	
	v=temp;
	reverse(all(v));
}

vector<int> f[100005];
vector<int> b[100005];

int qu[1000005];
int split[1000005];
long long ans[1000005];

void solve(int l,int r,vector<int> vl,vector<int> vr,ll cans,ll lu,ll ru){
	int m=l+r>>1;
	
	int ss=sz(ufds.roll);
	
	vector<int> vl1,vl2;
	vector<int> vr1,vr2;
	
	ll lans=0,rans=0;
	ll lu2=lu,ru2=ru;
	
	while (!vl.empty() || !vr.empty()){
		if (vr.empty() ||
			(!vl.empty() && qu[m]-ee[vl.back()].w<=ee[vr.back()].w-qu[m])){
			
			if (ufds.unions(ee[vl.back()].u,ee[vl.back()].v)){
				lans+=-ee[vl.back()].w;
				lu2++;
				
				vl1.pub(vl.back());
			}
			else{
				vl2.pub(vl.back());
			}
			vl.pob();
		}
		else{
			if (ufds.unions(ee[vr.back()].u,ee[vr.back()].v)){
				rans+=ee[vr.back()].w;
				ru2++;
				
				vr1.pub(vr.back());
			}
			else{
				vr2.pub(vr.back());
			}
			vr.pob();
		}
	}
	
	ans[m]=cans+lans+rans+lu2*qu[m]-ru2*qu[m];
	
	reverse(all(vl1)),reverse(all(vl2));
	reverse(all(vr1)),reverse(all(vr2));
	
	//cout<<"debug: "<<l<<" "<<m<<" "<<r<<endl;
	//for (auto it:vl1) cout<<it<<" "; cout<<endl;
	//for (auto it:vl2) cout<<it<<" "; cout<<endl;
	//for (auto it:vr1) cout<<it<<" "; cout<<endl;
	//for (auto it:vr2) cout<<it<<" "; cout<<endl;
	
	//vl1,vr1 are those things added at this stage
	ufds.rollback(ss);
	if (l!=m){
		for (auto it:vl1) ufds.unions(ee[it].u,ee[it].v);
		solve(l,m-1,vl2,vr1,cans+lans,lu2,ru);
		ufds.rollback(ss);
	}
	if (m!=r){
		for (auto it:vr1) ufds.unions(ee[it].u,ee[it].v);
		solve(m+1,r,vl1,vr2,cans+rans,lu,ru2);
		ufds.rollback(ss);
	}
}

namespace subtask3{
	vector<int> w[100005];
	int idx[100005];
	
	void solve(){
		int a,b,c;
		rep(x,0,m){
			w[ee[x].u].pub(ee[x].w);
		}
		
		rep(x,1,n) sort(all(w[x]));
		
		rep(x,0,q){
			long long ans=0;
			rep(x,1,n){
				while (idx[x]+1<sz(w[x]) && abs(w[x][idx[x]+1]-qu[x])<abs(w[x][idx[x]]-qu[x])){
					idx[x]++;
				}
				ans+=abs(w[x][idx[x]]-qu[x]);
			}
			
			cout<<ans<<endl;
		}
	}
}

signed main(){
	cin.tie(0);
	cout.tie(0);
	cin.sync_with_stdio(false);
	
	cin>>n>>m;
	rep(x,1,m+1) cin>>ee[x].u>>ee[x].v>>ee[x].w;
	cin>>q;
	rep(x,0,q) cin>>qu[x];
	
	if (m>1000 && q>20000){
		subtask3::solve();
		return 0;
	}
	
	sort(ee+1,ee+m+1,[](E i,E j){
		return i.w<j.w;
	});
	
	rep(x,1,m+1){
		f[x].pub(x);
		fix(f[x]);
		f[x+1]=f[x];
	}
	rep(x,m+1,1){
		b[x].pub(x);
		fix(b[x]);
		b[x-1]=b[x];
	}
	
	//rep(x,1,m+1) cout<<x<<" "; cout<<endl;
	//rep(x,1,m+1) cout<<ee[x].u<<" "; cout<<endl;
	//rep(x,1,m+1) cout<<ee[x].v<<" "; cout<<endl;
	
	//rep(x,1,m+1){
		//cout<<x<<": "; for (auto it:f[x]) cout<<it<<" "; cout<<endl;
	//}
	
	split[0]=1;
	rep(x,0,q){
		while (split[x]<=m && ee[split[x]].w<=qu[x]) split[x]++;
		split[x+1]=split[x];
	}
	
	//rep(x,0,q) cout<<split[x]<<" "; cout<<endl;
	
	rep(x,1,m+2){
		int l=lb(split,split+q,x)-split;
		int r=ub(split,split+q,x)-split-1;
		
		if (l<=r) solve(l,r,f[x-1],b[x],0,0,0);
	}
	
	rep(x,0,q) cout<<ans[x]<<endl;
}

Compilation message (stderr)

reconstruction.cpp: In function 'void solve(int, int, std::vector<int>, std::vector<int>, long long int, long long int, long long int)':
reconstruction.cpp:112:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  112 |  int m=l+r>>1;
      |        ~^~
reconstruction.cpp: In function 'void subtask3::solve()':
reconstruction.cpp:181:7: warning: unused variable 'a' [-Wunused-variable]
  181 |   int a,b,c;
      |       ^
reconstruction.cpp:181:9: warning: unused variable 'b' [-Wunused-variable]
  181 |   int a,b,c;
      |         ^
reconstruction.cpp:181:11: warning: unused variable 'c' [-Wunused-variable]
  181 |   int a,b,c;
      |           ^

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