Submission #699547

#	Time	Username	Problem	Language	Result	Execution time	Memory
699547		anonimy	Roadside Advertisements (NOI17_roadsideadverts)	C++14	100 / 100	157 ms	23296 KiB

roadsideadverts

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;

vector<vector<pll>> tree;
vector<pll> par;
vector<ll> depth, tin;
vector<vector<pll>> st;
ll logn;
const int Q_VERT = 5;
ll t = 0;

void dfs(ll v, ll p, ll wp)
{
	par[v] = { p, wp };
	depth[v] = depth[p] + 1;
	tin[v] = t++;

	for (ll i = 0; i < tree[v].size(); i++)
	{
		ll u = tree[v][i].first, w = tree[v][i].second;

		if (u == p) continue;

		dfs(u, v, w);
	}
}

ll getlog(ll n)
{
	ll ans = 0;
	while (n) ans++, n >>= 1;
	
	return ans;
}

bool comp(ll v, ll u)
{
	return tin[v] < tin[u];
}

ll LCA(ll v, ll u)
{
	if (depth[v] < depth[u]) swap(v, u);
	
	ll diff = depth[v] - depth[u];
	for (ll i = 0; diff; i++, diff >>= 1)
		if (diff & 1)
			v = st[i][v].first;

	for (ll i = logn - 1; i >= 0; i--)
		if (st[i][v].first != st[i][u].first)
			v = st[i][v].first, u = st[i][u].first;

	if (u != v)
		v = st[0][v].first;

	return v;
}

ll LCA5(vector<ll>& locations)
{
	ll ans = locations[0];
	for (ll i = 1; i < locations.size(); i++)
		ans = LCA(ans, locations[i]);

	return ans;
}

ll price(ll v, ll u)
{
	if (depth[v] < depth[u]) swap(v, u);

	ll diff = depth[v] - depth[u];
	ll ans = 0;
	for (ll i = 0; diff; i++, diff >>= 1)
		if (diff & 1)
			 ans+=st[i][v].second, v = st[i][v].first;

	return ans;
}

int main()
{
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	ll n;
	cin >> n;

	tree.resize(n);
	for (ll i = 0; i < n - 1; i++)
	{
		ll v, u, w;
		cin >> v >> u >> w;

		tree[v].push_back({ u, w });
		tree[u].push_back({ v, w });
	}

	par.resize(n);
	depth.resize(n, 0);
	tin.resize(n);
	dfs(0, 0, 0);

	logn = getlog(n) + 1;

	st.resize(logn, vector<pll>(n));
	for (ll i = 0; i < n; i++)
		st[0][i] = par[i];

	for(ll i=1;i<logn;i++)
		for (ll j = 0; j < n; j++)
		{
			st[i][j].first = st[i - 1][st[i - 1][j].first].first;
			st[i][j].second = st[i - 1][j].second + st[i - 1][st[i - 1][j].first].second;
		}

	ll q;
	cin >> q;


	while (q--)
	{
		vector<ll> locations(Q_VERT);
		for (ll i = 0; i < Q_VERT; i++)
			cin >> locations[i];

		sort(locations.begin(), locations.end(), comp);

		ll root = LCA5(locations);

		ll ans = price(root, locations[0]);
		for (ll i = 1; i < Q_VERT; i++)
			ans += price(locations[i], LCA(locations[i - 1], locations[i]));

		cout << ans << "\n";
	}
}

Compilation message (stderr)

roadsideadverts.cpp: In function 'void dfs(ll, ll, ll)':
roadsideadverts.cpp:24:19: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |  for (ll i = 0; i < tree[v].size(); i++)
      |                 ~~^~~~~~~~~~~~~~~~
roadsideadverts.cpp: In function 'll LCA5(std::vector<long long int>&)':
roadsideadverts.cpp:69:19: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |  for (ll i = 1; i < locations.size(); i++)
      |                 ~~^~~~~~~~~~~~~~~~~~

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