Submission #253210

#	Time	Username	Problem	Language	Result	Execution time	Memory
253210		nandonathaniel	Roadside Advertisements (NOI17_roadsideadverts)	C++14	100 / 100	232 ms	10372 KiB

roadsideadverts

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const int MAXN=5e4+5,LOG=16;
int depth[MAXN],pa[LOG][MAXN],a[5],par[MAXN],pref[MAXN];
vector<pii> adj[MAXN];

int find(int a){
	if(par[a]==a)return par[a];
	return par[a]=find(par[a]);
}

void join(int a,int b){
	int ortua=find(a);
	int ortub=find(b);
	par[ortub]=ortua;
}

void dfs(int now,int par){
	for(auto nxt : adj[now]){
		if(nxt.first==par)continue;
		pa[0][nxt.first]=now;
		for(int i=1;i<LOG;i++)pa[i][nxt.first]=pa[i-1][pa[i-1][nxt.first]];
		pref[nxt.first]=pref[now]+nxt.second;
		depth[nxt.first]=depth[now]+1;
		dfs(nxt.first,now);
	}
}

int LCA(int u,int v){
	if(depth[u]<depth[v])swap(u,v);
	int diff=depth[u]-depth[v];
	for(int i=LOG-1;i>=0;i--){
		if(diff&(1<<i))u=pa[i][u];
	}
	if(u==v)return u;
	for(int i=LOG-1;i>=0;i--){
		if(pa[i][u]!=pa[i][v]){
			u=pa[i][u];
			v=pa[i][v];
		}
	}
	return pa[0][u];
}

int dist(int u,int v){
	return pref[u]+pref[v]-2*pref[LCA(u,v)];
}

int main(){
	ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	int n,q,u,v,w;
	cin >> n;
	for(int i=1;i<n;i++){
		cin >> u >> v >> w;
		u++;v++;
		adj[u].push_back({v,w});
		adj[v].push_back({u,w});
	}
	dfs(1,-1);
	cin >> q;
	while(q--){
		vector<int> node;
		vector<pair<int,pii> > edge;
		for(int i=0;i<5;i++){
			cin >> a[i];
			a[i]++;
			node.push_back(a[i]);
			par[a[i]]=a[i];
		}
		for(int i=0;i<5;i++){
			for(int j=i+1;j<5;j++){
				int b=LCA(a[i],a[j]);
				node.push_back(b);
				par[b]=b;
			}
		}
		for(int i=0;i<node.size();i++){
			for(int j=i+1;j<node.size();j++){
				edge.push_back({dist(node[i],node[j]),{node[i],node[j]}});
			}
		}
		sort(edge.begin(),edge.end());
		int mstcost=0;
		for(auto isi : edge){
			int ortua=find(isi.second.first),ortub=find(isi.second.second);
			if(ortua!=ortub){
				join(ortua,ortub);
				mstcost+=isi.first;
			}
		}
		cout << mstcost << '\n';
	}
	return 0;
}

Compilation message (stderr)

roadsideadverts.cpp: In function 'int main()':
roadsideadverts.cpp:78:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<node.size();i++){
               ~^~~~~~~~~~~~
roadsideadverts.cpp:79:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j=i+1;j<node.size();j++){
                  ~^~~~~~~~~~~~

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