Submission #912185

#	Time	Username	Problem	Language	Result	Execution time	Memory
912185		arashMLG	Reconstruction Project (JOI22_reconstruction)	C++17	0 / 100	5066 ms	267828 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;

ll calc(int W) {
	edges.clear();
	ds.clear(n);
	fill(cnt,cnt+sz(edges) + 1,0);
	sex = 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 ++;
		}
	}
	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}};
	}
	int f;
	comp.pb(0);
	for(int i = 0 ; i < sq; i ++) {
		sort(all(comp)); f = sz(comp);
		comp.resize(unique(all(comp)) - comp.begin());
		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 val;
	bool change =true;
	while(q--) {
		int x; cin>>x;
		while(I+1 < sz(comp) && comp[I+1] <= x) {
			I++;
			change = true;
		}
		if(change) {
			val = calc(comp[I]);
		}
		int left= sex, right = (n-1)-sex;
		ll javab = val;
		//cerr<< "! " << javab << ' ' << left <<  ' ' << comp[I] << '\n';
		if(left != 0) javab += 1LL*left*(x-comp[I]);
		if(right!= 0) javab -= 1LL*right*(x-comp[I]);
		cout<<javab << '\n';
		change = false;
	}
	return 0;
}

Compilation message (stderr)

reconstruction.cpp: In function 'int32_t main()':
reconstruction.cpp:111:23: warning: 'val' may be used uninitialized in this function [-Wmaybe-uninitialized]
  111 |   if(left != 0) javab += 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