제출 #912253

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
912253		arashMLG	Reconstruction Project (JOI22_reconstruction)	C++17	0 / 100	5078 ms	9848 KiB

reconstruction

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

typedef long long       ll;
typedef pair<int,int>   pii;
typedef pair<ll,ll>     pll;

const int  N = 5e5 + 23;
const int sq = 50;
const ll inf = 1e18;


#define F          first
#define S          second
#define pb         push_back
#define sz(x)      ((int)x.size())
#define kill(x)    cout<< x , exit(0);
#define all(x)     x.begin(),x.end()
#define lc         (v<<1)
#define rc         ((v<<1)|1)

struct DSU {
	int par[N];
	int s[N];
	
	void clear(int n) {
		iota(par,par+n+1,0);
		fill(s,s+n+1,1);
	}
	
	int getPar(int v) {
		return (par[v] == v ? v : par[v] = getPar(par[v]));
	}
	
	bool merge(int v,int u) {
		v = getPar(v),u = getPar(u);
		if(v == u) return false;
		if(s[v] > s[u]) swap(v,u);
		par[v] = u;
		s[u] += s[v];
		return true;
	}
} ds;

int n,m;
vector<int> comp;
vector<int> edges;
pair<int,pii> E[N];
int cnt[N];


int fnd(int x) {
	return upper_bound(all(comp),x) - comp.begin() - 1;
}

int sex = 0;
int mos =0;

ll calc(int W) {
	edges.clear();
	ds.clear(n);
	fill(cnt,cnt+sz(edges) + 1,0);
	sex = 0;
	mos = 0;
	edges.resize(m);
	iota(all(edges),0);
	sort(all(edges),[&] (int x,int y) { return abs(E[x].F - W) < abs(E[y].F-W);});
	ll ans= 0;
	for(auto ind: edges) {
		auto [w,e] = E[ind];
		if(ds.merge(e.F,e.S)) {
			ans += abs(w-W);
			if(w < W) sex ++;
			if(w == W) mos ++;
		}
	}
	return ans;
}


int32_t main() {
	cin.tie(nullptr)->sync_with_stdio(false);
	cin>>n>>m;
	for(int i = 0 ; i < m; i ++) {
		int v,u,w; cin>>v>>u>>w;
		comp.pb(w);
		E[i]= {w,{v,u}};
	}
	comp.pb(0);
	comp.pb(int(1e9 + 9));
	int f=sz(comp);
	sort(all(comp));
	for(int i = 0 ; i+1 < f; i ++) comp.pb((comp[i] + comp[i+1])/2);
	sort(all(comp));
	comp.resize(unique(all(comp)) - comp.begin());
	int q; cin>>q;
	int I = 0;
	ll val1,val2;
	int sex1,sex2,mos1,mos2;
	bool change =true;
	while(q--) {
		int x; cin>>x;
		while(I+1 < sz(comp) && comp[I+1] <= x) {
			I++;
			change = true;
		}
		if(change) {
			val1 = calc(comp[I]);
			sex1 = sex;
			mos1 = mos;
			val2 = calc(comp[I+1]);
			sex2 = sex;
			mos2 = mos;
		}
		// chapi
		int left= sex1 + mos1, right = (n-1)-sex1-mos1;
		ll javab1 = val1;
		//cerr<< "! " << javab << ' ' << left <<  ' ' << comp[I] << '\n';
		if(left != 0) javab1 += 1LL*left*(x-comp[I]);
		if(right!= 0) javab1 -= 1LL*right*(x-comp[I]);
		// rasti
		left = sex2, right = (n-1)-sex2;
		ll javab2 = val2;
		if(left != 0) javab2 -= 1LL*left*(comp[I+1]-x);
		if(right!= 0) javab2 += 1LL*right*(comp[I+1]-x);
		//cerr<< javab1 << ' ' << javab2 << '\n';
		cout<<min(javab1,javab2) << '\n';
		change = false;
	}
	return 0;
}

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

reconstruction.cpp: In function 'int32_t main()':
reconstruction.cpp:99:21: warning: variable 'mos2' set but not used [-Wunused-but-set-variable]
   99 |  int sex1,sex2,mos1,mos2;
      |                     ^~~~
reconstruction.cpp:116:26: warning: 'mos1' may be used uninitialized in this function [-Wmaybe-uninitialized]
  116 |   int left= sex1 + mos1, right = (n-1)-sex1-mos1;
      |                          ^~~~~
reconstruction.cpp:124:31: warning: 'sex2' may be used uninitialized in this function [-Wmaybe-uninitialized]
  124 |   if(left != 0) javab2 -= 1LL*left*(comp[I+1]-x);
      |                               ^~~~
reconstruction.cpp:116:39: warning: 'sex1' may be used uninitialized in this function [-Wmaybe-uninitialized]
  116 |   int left= sex1 + mos1, right = (n-1)-sex1-mos1;
      |                                  ~~~~~^~~~~
reconstruction.cpp:124:24: warning: 'val2' may be used uninitialized in this function [-Wmaybe-uninitialized]
  124 |   if(left != 0) javab2 -= 1LL*left*(comp[I+1]-x);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
reconstruction.cpp:119:24: warning: 'val1' may be used uninitialized in this function [-Wmaybe-uninitialized]
  119 |   if(left != 0) javab1 += 1LL*left*(x-comp[I]);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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