Tietoverkko

#include <math.h>
#include <iostream>
#include <map>
#include <vector>
#define L long long
using namespace std;

void definef();
vector<L> erittely(L k);
pair<L,L> ylos(L a, L k);
pair<L, L> ylos(L a, L k, L c);
pair<L,L> f(L x, L k);
L etsi(L a, L b);


map<L, pair<pair<L, L>, L>> m = { {1, { {0, 0}, 1 }} };
map<L, map<L, pair<L, L>>> fx;

L n, ddef = 0, deri1 = 0, deri2 = 0, dylo = 0, dylo2 = 0, df = 0, detsi = 0;

int main()
{
	L a, b, x, k = 0;
	cin >> n;

	L kerros = 1;
	L e = 0;
	for (L i = 0; i < n - 1; i++)
	{
		cin >> a >> b >> x;
		if (a < e) kerros = m[a].second;
		e = b;
		kerros++;

		m[b] = { {a, x}, kerros };
		//cout << "b: " << b << " a: " << a << " x: " << x << " kerros: " << kerros << "\n";
	}

	definef();

	k += etsi(1, n);
	for (L i = 1; i < n; i++)
	{
		k += etsi(i, i + 1);
		if (i < n - 1 && i != 1) k += etsi(i, n);
		if (i < n - 1 && i != 1) k += etsi(1, n - (i - 1));
		if (i + 1 < n - i - 1) k += etsi(i + 1, n - i);
	}

	cout << k << "\n";
	// cout << "ddef: " << ddef << " deri: " << deri1 << " deri2: " << deri2 << " dylo: " << dylo << " dylo2: " << dylo2 << " df: " << df << " detsi: " << detsi << "\n";
}

void definef()
{
	for (L i = 1; i <= n; i *= 2)
	{
		for (L j = 1 + i; j <= n; j++)
		{
			ddef++;
			//cout << "ddef++: " << ddef << "\n";
			pair<L,L> p = ylos(j, i);
			fx[i][j] = p;
			//cout << "i: " << i << " j: " << j << " p.first: " << p.first << " p.second: " << p.second << "\n";
		}
	}
}

vector<L> erittely(L k)
{
	vector<L> komponentit;
	L sum = 0;
	L i = 0;
	L kom = 0;
	while (true)
	{
		kom = powl(2, i);
		deri1++;
		//cout << "deri1++: " << deri1 << "\n";
		if (kom > k)
		{
			kom = powl(2, i - 1);
			komponentit.push_back(kom);
			sum = kom;
			break;
		}
		else if (kom == k)
		{
			komponentit.push_back(kom);
			sum = kom;
			break;
		}
		i++;
	}
	while (sum != k)
	{
		deri2++;
		//cout << "deri2++: " << deri2 << "\n";
		kom = kom / 2;
		if (kom + sum <= k)
		{
			komponentit.push_back(kom);
			sum += kom;
		}
	}
	return komponentit;
}

pair<L,L> ylos(L a, L k)
{
	L minx = 1000000000;
	for (L i = 0; i < k; i++)
	{
		dylo++;
		//cout << "dylo++: " << dylo << "\n";
		if (a == 1) break;
		if (minx == 1) break;
		if (m[a].first.second < minx) minx = m[a].first.second;
		a = m[a].first.first;
	}

	if (minx == 1000000000)
	{
		pair<L, L> p = { a, 0 };
		return p;
	}
	pair<L, L> p = { a, minx };
	return p;
}

pair<L, L> ylos(L a, L k, L c)
{
	L minx = 1000000000;
	for (L i = 0; i < k; i++)
	{
		dylo2++;
		//cout << "dylo2++: " << dylo2 << "\n";
		if (a == 1) break;
		if (minx == 1) break;
		if (m[a].first.second < minx) minx = m[a].first.second;
		a = m[a].first.first;
	}
	if (c < minx) minx = c;

	if (minx == 1000000000)
	{
		pair<L, L> p = { a, 0 };
		return p;
	}
	pair<L, L> p = { a, minx };
	return p;
}

pair<L,L> f(L x, L k)
{
	//cout << "x: " << x << " k: " << k;
	vector<L> komponentit = erittely(k);
	L c = 0;
	for (auto kom : komponentit)
	{
		df++;
		//cout << "df++: " << df << "\n";
		c = fx[kom][x].second;
		if (fx[kom][x].first == 1 || c == 1) break;
		x = fx[kom][x].first;
	}
	//cout << "fc: " << c << "\n";
	return { x, c };
}

L etsi(L a, L b)
{
	pair<L, L> p;

	//cout << "a: " << a << " b: " << b << "\n";
	L c = 1000000000, c2 = 1000000000, d = m[a].second - m[b].second;
	if (d < 0)
	{
		p = f(b, -d);
		b = p.first;
		c = p.second;
	}
	else if (d > 0)
	{
		p = f(a, d);
		a = p.first;
		c = p.second;
	}


	if (a == b)
	{
		if (c < c2) return c;
		else return c2;
	}
	else
	{
		while (a != b)
		{
			detsi++;
			//cout << "detsi++: " << detsi << "\n";
			if (a != 1) 
			{
				p = ylos(a, 1, c);
				a = p.first;
				c = p.second;
			}

			if (b != 1) 
			{ 
				p = ylos(b, 1, c2);
				b = p.first;
				c2 = p.second;
			}

			if (c == 1 || c2 == 1) break;
		}
	}
	//cout << "c: " << c << " tai " << c2 <<"\n";
	if (c == 0 && c2 != 0) return c2;
	else if (c != 0 && c2 == 0) return c;
	else if (c < c2) return c;
	else if (c > c2) return c2;
	return c;
}

Test 1

Group: 1, 2, 3

Verdict: WRONG ANSWER

Test 2

Group: 2, 3

Verdict: WRONG ANSWER

Test 3

Group: 3

Verdict: TIME LIMIT EXCEEDED