Submission #537332

#	Time	Username	Problem	Language	Result	Execution time	Memory
537332		ac2hu	Roadside Advertisements (NOI17_roadsideadverts)	C++14	100 / 100	76 ms	18508 KiB

roadsideadverts

#include <bits/stdc++.h>
using namespace std;
void setIO(string name) {
	#ifdef DEBUG
	#else 
	ios_base::sync_with_stdio(0); cin.tie(0);
	freopen((name+".in").c_str(),"r",stdin);
	freopen((name+".out").c_str(),"w",stdout);
	#endif
}
#define int long long 
const int N = 5e4 + 10;
const int LG = log2(N) + 10;
int n,q,timer = 0,l;
vector<pair<int,int>> adj[N];
// array<int,3> edges[N];
int rdist[N],tin[N],tout[N], lcst[N][LG];
void dfs0(int i,int p){
	tin[i] = ++timer;
	lcst[i][0] = p;
	for(int _ = 1;_<=l;_++){
		lcst[i][_] = lcst[lcst[i][_ - 1]][_ - 1];
	}
	for(auto e : adj[i]){
		if(e.first == p)continue;
		rdist[e.first] = rdist[i] + e.second;
		dfs0(e.first,i);
	}
	tout[i] = ++timer;
}
inline int is_ansestor(int u,int v){
	return (tin[u] <= tin[v] && tout[u] >= tout[v]);
}
int lca(int a,int b){
	if(is_ansestor(a,b))
		return a;
	if(is_ansestor(b,a))
		return b;
	for(int i  =l;i>=0;i--){
		if(!is_ansestor(lcst[a][i], b))
			a = lcst[a][i];
	}
	return lcst[a][0];
}
signed main() {
	iostream::sync_with_stdio(false);
	cin.tie(nullptr);cout.tie(nullptr);
	cin >> n;
	l = ceil(log2(n));
	for(int i = 0;i<n - 1;i++){
		int a,b,w;cin >> a >> b >> w;
		adj[a].push_back({b,w});
		adj[b].push_back({a,w});
		// edges[i] = {a,b,w};
	}
	rdist[0] = 0;
	dfs0(0,0);
	int q;cin >> q;
	while(q--){
		array<int,5> nums;
		for(auto &e : nums)cin >> e;
		sort(nums.begin(),nums.end(), [&](int a,int b){
			return tin[a] < tin[b];
		});
		int ans = 0;
		for(unsigned i = 0;i<nums.size();i++){
			int j = (i + 1)%nums.size();
			int a = nums[i],b = nums[j];
			int anc = lca(a,b);
			ans += rdist[a] + rdist[b] - 2*rdist[anc];
		}
		ans /= 2;
		cout << ans << "\n";
	}
}

Compilation message (stderr)

roadsideadverts.cpp: In function 'void setIO(std::string)':
roadsideadverts.cpp:7:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    7 |  freopen((name+".in").c_str(),"r",stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
roadsideadverts.cpp:8:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    8 |  freopen((name+".out").c_str(),"w",stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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