oj.uz

Submission #293169

# Submission time Handle Problem Language Result Execution time Memory
293169 2020-09-07T17:22:15 Z Berted Roadside Advertisements (NOI17_roadsideadverts) C++14
100 / 100
 170 ms 14640 KB 
#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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 170 ms 13544 KB Output is correct
2 Correct 124 ms 14632 KB Output is correct
3 Correct 122 ms 14572 KB Output is correct
4 Correct 138 ms 14584 KB Output is correct
5 Correct 121 ms 14632 KB Output is correct
6 Correct 123 ms 14568 KB Output is correct
7 Correct 119 ms 14572 KB Output is correct
8 Correct 120 ms 14576 KB Output is correct
9 Correct 113 ms 14640 KB Output is correct
10 Correct 119 ms 14568 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 12148 KB Output is correct
2 Correct 56 ms 13928 KB Output is correct
3 Correct 60 ms 13928 KB Output is correct
4 Correct 65 ms 13928 KB Output is correct
5 Correct 60 ms 13872 KB Output is correct
6 Correct 58 ms 14060 KB Output is correct
7 Correct 62 ms 13928 KB Output is correct
8 Correct 57 ms 13932 KB Output is correct
9 Correct 59 ms 13928 KB Output is correct
10 Correct 61 ms 13928 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 170 ms 13544 KB Output is correct
3 Correct 124 ms 14632 KB Output is correct
4 Correct 122 ms 14572 KB Output is correct
5 Correct 138 ms 14584 KB Output is correct
6 Correct 121 ms 14632 KB Output is correct
7 Correct 123 ms 14568 KB Output is correct
8 Correct 119 ms 14572 KB Output is correct
9 Correct 120 ms 14576 KB Output is correct
10 Correct 113 ms 14640 KB Output is correct
11 Correct 119 ms 14568 KB Output is correct
12 Correct 36 ms 12148 KB Output is correct
13 Correct 56 ms 13928 KB Output is correct
14 Correct 60 ms 13928 KB Output is correct
15 Correct 65 ms 13928 KB Output is correct
16 Correct 60 ms 13872 KB Output is correct
17 Correct 58 ms 14060 KB Output is correct
18 Correct 62 ms 13928 KB Output is correct
19 Correct 57 ms 13932 KB Output is correct
20 Correct 59 ms 13928 KB Output is correct
21 Correct 61 ms 13928 KB Output is correct
22 Correct 136 ms 13456 KB Output is correct
23 Correct 79 ms 12652 KB Output is correct
24 Correct 115 ms 14312 KB Output is correct
25 Correct 123 ms 14312 KB Output is correct
26 Correct 124 ms 14216 KB Output is correct
27 Correct 116 ms 14312 KB Output is correct
28 Correct 116 ms 14316 KB Output is correct
29 Correct 117 ms 14316 KB Output is correct
30 Correct 119 ms 14316 KB Output is correct
31 Correct 115 ms 14312 KB Output is correct