Submission #676474

#	Time	Username	Problem	Language	Result	Execution time	Memory
676474		penguin133	Roadside Advertisements (NOI17_roadsideadverts)	C++17	100 / 100	239 ms	16596 KiB

roadsideadverts

#include <bits/stdc++.h>
using namespace std;
#define int long long
int mini = 1e18, ans = 1;
const int mod= 1e9 + 7;
int par[20][50005], depth[50005], dist[50005];
vector<pair<int, int> > v[50005];
void dis(int p, int cost){
	if(p == 0 && cost)return;
	if(!dist[p])dist[p] = cost;
	else return;
	for(auto i : v[p])dis(i.first, cost + i.second);
}
void dfs(int x, int p, int dep){
	par[0][x] = p;
	depth[x] = dep;
	for(auto i : v[x]){
		if(i.first != p)dfs(i.first, x, dep + 1);
	}
}
int lca(int a, int b){
	if(depth[a] > depth[b])swap(a, b);
	int diff = depth[b] - depth[a];
	for(int i=0;i<=19;i++){
		if(diff & (1<<i))b = par[i][b];
	}
	if(a == b)return a;
	for(int i=19;i>=0;i--){
		if(par[i][a] != par[i][b]){
			a = par[i][a], b = par[i][b];
		}
	}
	return par[0][a];
}
int p[100005];
int getr(int x){
	if(p[x] == x)return x;
	else return p[x] = getr(p[x]);
}
void merge(int a, int b){
	a = getr(a); b = getr(b);
	if(a != b)p[b] = a;
}
main(){
	ios::sync_with_stdio(0);cin.tie(0);
	int n;cin >> n;
	for(int i=1;i<n;i++){
		int a,b,c;
		cin >> a >> b >> c;
		v[a].push_back({b,c});
		v[b].push_back({a,c});
	}
	dis(0, 0);
	dfs(0, -1, 1);
	for(int i=1;i<=19;i++){
		for(int j=0;j<n;j++)par[i][j] = par[i-1][par[i-1][j]];
	}
	int q;cin >> q;
	while(q--){
		vector<int>temp;
		for(int i=0;i<5;i++){
			int a;cin >> a; temp.push_back(a);
		}
		for(int i=0;i<5;i++){
			for(int j=0;j<5;j++)temp.push_back(lca(temp[i], temp[j]));
		}
		sort(temp.begin(),temp.end());
		temp.erase(unique(temp.begin(),temp.end()),temp.end());
		vector<pair<int, pair<int, int> > >adj;
		for(int i=0;i<(int)temp.size();i++){
			for(int j=0;j<(int)temp.size();j++)adj.push_back({dist[temp[i]] + dist[temp[j]] - 2 * dist[lca(temp[i], temp[j])], {temp[i], temp[j]}});
		}
		int ans =0 ;
		sort(adj.begin(), adj.end());
		for(int i=0;i<(int)temp.size();i++)p[temp[i]] = temp[i];
		for(auto i : adj){
			int x = i.first,y  =i.second.first, z= i.second.second;
			if(getr(y) == getr(z))continue;
			merge(y,z);
			ans += x;
		}
		cout << ans << '\n';
	}
}

Compilation message (stderr)

roadsideadverts.cpp:44:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   44 | main(){
      | ^~~~

• Subtask 1: 7 / 7
• Subtask 2: 23 / 23
• Subtask 3: 40 / 40
• Subtask 4: 30 / 30