oj.uz

Submission #912183

# Submission time Handle Problem Language Result Execution time Memory
912183 2024-01-19T08:01:50 Z arashMLG Reconstruction Project (JOI22_reconstruction) C++17
0 / 100
 5000 ms 269980 KB 
#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 = 10;
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

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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 3 ms 6576 KB Output is correct
4 Incorrect 3 ms 6748 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 3 ms 6576 KB Output is correct
4 Incorrect 3 ms 6748 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6612 KB Output is correct
3 Correct 3 ms 6748 KB Output is correct
4 Execution timed out 5042 ms 269980 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 3 ms 6576 KB Output is correct
4 Incorrect 3 ms 6748 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 3 ms 6576 KB Output is correct
4 Incorrect 3 ms 6748 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 3 ms 6576 KB Output is correct
4 Incorrect 3 ms 6748 KB Output isn't correct
5 Halted 0 ms 0 KB -