CSES - Datatähti 2022 alku - Results
Submission details
Task:Tietoverkko (Network)
Sender:Sahari Kempo
Submission time:2021-10-17 01:35:34
Language:C++17
Status:READY
Result:0
Feedback
groupverdictscore
#10
#20
#30
Test results
testverdicttimegroup
#10.57 s1, 2, 3details
#20.65 s2, 3details
#3--3details

Compiler report

input/code.cpp: In function 'std::vector<long long int> erittely(long long int)':
input/code.cpp:89:3: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   if (kom + sum <= k);
   ^~
input/code.cpp:90:3: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   {
   ^
input/code.cpp: In function 'long long int etsi(long long int, long long int)':
input/code.cpp:156:28: warning: left operand of comma operator has no effect [-Wunused-value]
  if (d < 0)  a, c = f(b, -d);
                            ^
input/code.cpp:157:31: warning: left operand of comma operator has no effect [-Wunused-value]
  else if (d > 0) b, c = f(a, d);
                               ^
input/code.cpp:187:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

Code

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

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

void definef()
{
	for (L i = 1; i <= n; i *= 2)
	{
		for (L j = 1 + i; j <= n; j++)
		{
			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);
		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)
	{
		kom = kom / 2;
		if (kom + sum <= k);
		{
			kom *= 2;
			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++)
	{
		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++)
	{
		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)
	{
		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)
{
	L c = 1000000000, c2 = 1000000000, d = m[a].second - m[b].second;
	if (d < 0)  a, c = f(b, -d);
	else if (d > 0) b, c = f(a, d);

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

Test details

Test 1

Group: 1, 2, 3

Verdict:

input
100
1 2 74
1 3 100
2 4 50
3 5 40
...

correct output
88687

user output
(empty)

Test 2

Group: 2, 3

Verdict:

input
5000
1 2 613084013
1 3 832364259
2 4 411999902
3 5 989696303
...

correct output
1103702320243776

user output
(empty)

Test 3

Group: 3

Verdict:

input
200000
1 2 613084013
1 3 832364259
2 4 411999902
3 5 989696303
...

correct output
1080549209850010931

user output
(empty)