oj.uz

Submission #645202

# Submission time Handle Problem Language Result Execution time Memory
645202 2022-09-26T12:23:03 Z google Toll (APIO13_toll) C++17
16 / 100
 1 ms 280 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 0x3F3F3F3F3F3F3F3F;
ll N,M,K,a,b;
vector<pair<ll,pair<ll,ll>>> G,Mst;
vector<map<ll,ll>> Gr;
struct dsu{
	vector<int> p,sz;
	void init(int N){
		p.resize(N+1);
		iota(p.begin(),p.end(),0);
		sz.assign(N+1,1);
	}
	int findp(int a){
		if (p[a] == a) return a;
		return p[a] = findp(p[a]);
	}
	bool same(int a, int b){
		return findp(a) == findp(b);
	}
	void unite(int a, int b){
		a = findp(a), b = findp(b);
		if (sz[a] < sz[b]) swap(a,b);
		sz[a] += sz[b];
		p[b] = a;
	}
};
ll mst(vector<pair<ll,pair<ll,ll>>> &G, vector<pair<ll,pair<ll,ll>>> &mend){
	dsu ds;
	ds.init(N);
	ll ans = 0;
	for (auto [t,a]:mend){
		if (ds.same(a.first,a.second)) continue;
		ds.unite(a.first,a.second);
		Mst.push_back({t,a});
		ans += t;
	}
	for (auto [t,a]:G){
		if (ds.same(a.first,a.second)) continue;
		ds.unite(a.first,a.second);
		Mst.push_back({t,a});
		ans += t;
	}
	return ans;
}
vector<ll> dp,sz,dist;
void dfs(int a,int p = -1){
	dp[a] = sz[a];
	if (~p) dist[a] = dist[p]+1;
	else dist[a] = 0;
	for (auto aa:Gr[a]){
		if (aa.first == p) continue;
		dfs(aa.first,a);
		dp[a] += dp[aa.first];
	}
}
int main(){
	cin.tie(0)->sync_with_stdio(0);
	cin >> N >> M >> K;
	G.resize(M);
	for (int i = 0;i<M;i++) cin >> G[i].second.first >> G[i].second.second >> G[i].first;
	sort(G.begin(),G.end());
	ll reg = mst(G,G),price;
	for (int i = 0;i<K;i++){
		cin >> a >> b;
		ll l = 0,r = 1e6+1,mid;
		while (l<r){
			Mst.clear();
			mid = (l+r+1)/2;
			vector<pair<ll,pair<ll,ll>>> t = {{mid,{a,b}}};
			if (mst(G,t) > reg) r = mid-1;
			else l = mid;
		}
		price = l;
	}
	Gr.resize(N+1);
	for (auto [a,b]:Mst){
		Gr[b.first][b.second] = a;
		Gr[b.second][b.first] = a;
	}
	dp.assign(N+1,0);
	sz.assign(N+1,0);
	dist.assign(N+1,0);
	for (int i = 1;i<=N;i++) cin >> sz[i];
	dfs(1);
	if (dist[b] > dist[a]) swap(a,b);
	cout << dp[a]*price;
	return 0;
}

Compilation message

toll.cpp: In function 'int main()':
toll.cpp:88:16: warning: 'price' may be used uninitialized in this function [-Wmaybe-uninitialized]
   88 |  cout << dp[a]*price;
      |                ^~~~~

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 280 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 280 KB Output is correct
3 Incorrect 1 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 280 KB Output is correct
3 Incorrect 1 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 280 KB Output is correct
3 Incorrect 1 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 280 KB Output is correct
3 Incorrect 1 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -