Submission #1052695

#	Time	Username	Problem	Language	Result	Execution time	Memory
1052695		_rain_	Roadside Advertisements (NOI17_roadsideadverts)	C++14	100 / 100	44 ms	21184 KiB

roadsideadverts

#include<bits/stdc++.h>
using namespace std;
using i64 = long long;

#define int long long
const int maxn = 1e5;
const int maxlog = 16;
vector<pair<int,int>> g[maxn+2];
int sta[maxn+2] , fin[maxn+2] , timedfs = 0 , n;
int par[maxn+2][maxlog+2] , h[maxn+2] , v[maxn+2] , d[maxn+2];

	void dfs(int u , int p)
	{
		sta[u] = ++timedfs;
		h[u] = h[p]+1;
		par[u][0] = p;
		for (int i = 1; i <= maxlog; ++i)
			par[u][i] = par[par[u][i - 1]][i - 1];
		for (auto& v : g[u])
			if(v.first != p)
			{
				d[v.first] = d[u] + v.second;
				dfs(v.first , u);
			}
		fin[u] = timedfs;
		return;
	}
	int LCA(int u , int v)
	{
		if (h[u] < h[v]) swap(u,v);
		for (int i = maxlog; i >= 0; --i)
			if (h[par[u][i]] >= h[v])
				u = par[u][i];
		if (u==v) return u;
		for (int i = maxlog; i >= 0; --i)
			if (par[u][i]!=par[v][i])
				u = par[u][i] , v = par[v][i];
		return par[u][0];
	}
bool parent(int u , int lca)
{
	return sta[lca] <= sta[u] && sta[u] <= fin[lca];
}

bool cmp(int x , int y)
{
	return sta[x] < sta[y];
}

int32_t main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	#define name "main"
	if (fopen(name".inp","r"))
	{
		freopen(name".inp","r",stdin);
		freopen(name".out","w+",stdout);
	}
	cin >> n;
	for (int i = 1; i < n; ++i)
			{
				int u , v , w; cin >> u >> v >> w;
				++u,++v;
				g[u].push_back({v,w});
				g[v].push_back({u,w});
			}
	dfs(1,0);
	int q; cin >> q;
	while(q--)
	{
		int numv = 5;
		vector<int> vert;
		for (int i = 1; i <= numv; ++i) {
			cin >> v[i]; ++v[i];
			vert.push_back(v[i]);
		}
		sort(v+1,v+numv+1,cmp);
		for (int i = 2;i <= numv; ++i) vert.push_back(LCA(v[i],v[i-1]));
		sort(vert.begin(),vert.end(),cmp); vert.resize(unique(vert.begin(),vert.end()) - vert.begin());
		vector<int> lis;
		i64 answer = 0;
		lis.push_back(vert[0]);
		for (int i = 1; i < vert.size(); ++i)
		{
			while (lis.size() && !parent(vert[i],lis.back())) lis.pop_back();
			if (lis.size())
			{
				// cout << lis.back() << ' ' << vert[i] << '\n';
				answer += d[vert[i]] - d[lis.back()];
			}
			lis.push_back(vert[i]);
		}
		cout << answer << '\n';
	}
}

Compilation message (stderr)

roadsideadverts.cpp: In function 'int32_t main()':
roadsideadverts.cpp:84:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |   for (int i = 1; i < vert.size(); ++i)
      |                   ~~^~~~~~~~~~~~~
roadsideadverts.cpp:57:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |   freopen(name".inp","r",stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
roadsideadverts.cpp:58:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |   freopen(name".out","w+",stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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