Submission #293169

#	Time	Username	Problem	Language	Result	Execution time	Memory
293169		Berted	Roadside Advertisements (NOI17_roadsideadverts)	C++14	100 / 100	170 ms	14640 KiB

roadsideadverts

#include <iostream>
#include <vector>
#define pii pair<int,int>
#define mkp make_pair
#define fst first
#define snd second
#define vpi vector<pii>
#define epb emplace_back
using namespace std;

vector<vpi> adj;vector<int> tmp;
int v,sp[2][50001][20]={},q,h[50001]={},tplca,tplgth,tpa,tpb;

void dfs(int u,int p,int pw,int ht)
{
	sp[0][u][0] = p;sp[1][u][0] = pw;h[u] = ht;
	for (int i=1;i<20;i++)
	{
		if (sp[0][u][i-1]!=-1)
		{
			sp[0][u][i] = sp[0][sp[0][u][i-1]][i-1];
			sp[1][u][i] = sp[1][u][i-1] + sp[1][sp[0][u][i-1]][i-1];
		}
		else {break;}
	}
	for (auto v:adj[u])
	{
		if (v.fst!=p)
		{
			dfs(v.fst,u,v.snd,ht+1);
		}
	}
}

pii lca(int a,int b)
{
	int diff, ptr = 0,crl = 0;
	if (h[a]>h[b]) {swap(a,b);}
	
	diff = h[b]-h[a];
	while (diff)
	{
		if (diff%2) 
		{
			crl += sp[1][b][ptr];
			b = sp[0][b][ptr];
		}
		ptr++;diff=diff>>1;
	
	}

	while (a!=b)
	{
		for (int j=19;j>=0;j--)
		{
			if (sp[0][b][j] != sp[0][a][j]) 
			{
				crl += sp[1][a][j]; crl+=sp[1][b][j];
				a = sp[0][a][j]; b = sp[0][b][j];

			}
			else if (j==0) 
			{
				crl+=sp[1][a][0]; crl+=sp[1][b][0];
				a = sp[0][a][0]; b = a;
			}
		}
	}

	return mkp(a,crl);
}
int main()
{
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);

	cin>>v;

	for (int i=0;i<v;i++) 
	{
		adj.epb(vpi());
		for (int j=0;j<20;j++) 
		{
			sp[0][i][j]=-1;
			sp[1][i][j]=0;
		}
	}

	for (int i=0;i<v-1;i++)
	{
		int a,b,c;cin>>a>>b>>c;
		adj[a].epb(b,c);
		adj[b].epb(a,c);
	}

	dfs(0,-1,0,0);

	cin>>q;
	
	for (int i=0;i<q;i++)
	{
		int rslt = 0;

		for (int j=0;j<5;j++) {int a;cin>>a;tmp.epb(a);}
		
		for (int l=4;l;l--)
		{
			tplca = -1;vector<int> tmp2;
			for (int j=0;j<=l;j++)
			{
				for (int k=j+1;k<=l;k++)
				{
					pii rslt = lca(tmp[j],tmp[k]);
					//cout<<j<<" "<<k<<" "<<rslt.fst<<" "<<rslt.snd<<"\n";
					if (tplca==-1) {tplca = rslt.fst; tplgth = rslt.snd; tpa=j;tpb = k;}
					else if (h[rslt.fst]>h[tplca]) {tplca = rslt.fst; tplgth = rslt.snd; tpa=j;tpb = k;}
				}
			}
			for (int j=0;j<=l;j++)
			{
				if (j!=tpa&&j!=tpb) {tmp2.epb(tmp[j]);}
			}
			tmp2.epb(tplca);
			tmp=tmp2;
			//for (int i=0;i<l;i++) {cout<<tmp[i]<<" ";}cout<<"  "<<tpa<<" "<<tpb<<"\n";
			rslt+=tplgth;
		}

		cout<<rslt<<"\n";

		tmp.clear();
	}
	return 0;
}

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