Submission #951636

#	Time	Username	Problem	Language	Result	Execution time	Memory
951636		pcc	Reconstruction Project (JOI22_reconstruction)	C++17	14 / 100	5044 ms	41888 KiB

reconstruction

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

#define ll long long
#define al3 array<ll,3>
#define pll pair<ll,ll>
#define fs first
#define sc second

const int mxn = 1e5+10;
int N,M,Q;
array<ll,3> edges[mxn];

struct DSU{
	int dsu[550],sz[550];
	void init(int n){
		for(int i = 0;i<=n;i++){
			dsu[i] = i;
			sz[i] = 1;
		}
	}
	int root(int k){
		return k == dsu[k]?k:dsu[k] = root(dsu[k]);
	}
	void onion(int a,int b){
		 a = root(a),b = root(b);
		 if(a == b)return;
		 if(sz[a]<sz[b])swap(a,b);
		 dsu[b] = a;
		 sz[a] += sz[b];
		 return;
	}
};

DSU dsu;

namespace S1{
	void solve(){
		ll K;
		cin>>K;
		sort(edges,edges+M,[&](al3 &a,al3 &b){return abs(a[0]-K)<abs(b[0]-K);});
		dsu.init(N);
		ll ans = 0;
		for(int i = 0;i<M;i++){
			auto [w,a,b] = edges[i];
			if(dsu.root(a) == dsu.root(b))continue;
			ans += abs(w-K);
			dsu.onion(a,b);
		}
		cout<<ans<<'\n';
		return;
	}
}

namespace S2{
	vector<pll> req;
	ll ans[mxn*10];
	vector<int> v[550];
	int ptr[550];
	void solve(){
		for(int i = 0;i<M;i++){
			v[min(edges[i][1],edges[i][2])].push_back(edges[i][0]);
		}
		for(int i = 1;i<=N;i++){
			sort(v[i].begin(),v[i].end());
		}
		for(int i = 1;i<=Q;i++){
			ll k;
			cin>>k;
			req.push_back(pll(k,i));
		}
		sort(req.begin(),req.end());
		for(auto &i:req){
			ll tans = 0;
			for(int j = 1;j<N;j++){
				while(ptr[j]+1<v[j].size()&&abs(v[j][ptr[j]]-i.fs)>=abs(v[j][ptr[j]+1]-i.fs))ptr[j]++;
				tans += abs(v[j][ptr[j]]-i.fs);
			}
			ans[i.sc] = tans;
		}
		for(int i = 1;i<=Q;i++){
			cout<<ans[i]<<'\n';
		}
		return;
	}
}

namespace S3{
	vector<pll> req;
	ll ans[mxn*10];
	void solve(){
		sort(edges,edges+M);
		int pt = 0;
		for(int i = 1;i<=Q;i++){
			int K;
			cin>>K;
			req.push_back(pll(K,i));
		}
		sort(req.begin(),req.end());
		for(auto &i:req){
			dsu.init(N);
			while(pt<M&&edges[pt][0]<=i.fs)pt++;
			int pl = pt-1,pr = pt;
			ll tans = 0;
			while(pl>=0||pr<M){
				bool isl = false;
				if(pr >= M)isl = true;
				else if(pl < 0)isl = false;
				else if(i.fs-edges[pl][0]<edges[pr][0]-i.fs)isl = true;
				if(isl){
					if(dsu.root(edges[pl][1]) != dsu.root(edges[pl][2])){
						dsu.onion(edges[pl][1],edges[pl][2]);
						tans += i.fs-edges[pl][0];
					}
					pl--;
				}
				else{
					if(dsu.root(edges[pr][1]) != dsu.root(edges[pr][2])){
						dsu.onion(edges[pr][1],edges[pr][2]);
						tans += edges[pr][0]-i.fs;
					}
					pr++;
				}
			}
			ans[i.sc] = tans;
		}
		for(int i = 1;i<=Q;i++){
			cout<<ans[i]<<'\n';
		}
		return;
	}
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>N>>M;
	for(int i = 0;i<M;i++){
		int a,b,c;
		cin>>a>>b>>c;
		edges[i] = array<ll,3>({c,a,b});
	}
	cin>>Q;
	if(Q<=10)while(Q--)S1::solve();
	else if(M<=1000)S3::solve();
	else S2::solve();
}

Compilation message (stderr)

reconstruction.cpp: In function 'void S2::solve()':
reconstruction.cpp:78:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |     while(ptr[j]+1<v[j].size()&&abs(v[j][ptr[j]]-i.fs)>=abs(v[j][ptr[j]+1]-i.fs))ptr[j]++;
      |           ~~~~~~~~^~~~~~~~~~~~

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