제출 #951580

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
951580		pcc	Reconstruction Project (JOI22_reconstruction)	C++17	14 / 100	1709 ms	46396 KiB

reconstruction

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

#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;
	}
};

namespace S1{
	DSU dsu;
	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;
	}
}

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 S2::solve();
}

컴파일 시 표준 에러 (stderr) 메시지

reconstruction.cpp: In function 'void S2::solve()':
reconstruction.cpp:75:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |     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