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);
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 };
	}

	definef();

	for (L i = 1; i < n; i++)
	{
		k += etsi(i, n);
		if (n - i > 1) k += etsi(n - i, 1);
		if(i + 1 < n - i) 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;
		}
	}
}

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;
}

L f(L x, L 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;
	}
	return c;
}

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

	if (a == b)
	{
		c = m[a].first.second;
	}
	else
	{
		pair<L, L> p;
		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 << "\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