CSES - DatatÃ¤hti 2022 alku - Results
 Task: Tietoverkko Sender: Sahari Kempo Submission time: 2021-10-17 01:43:05 +0300 Language: C++17 Status: READY Result: 0
Feedback
groupverdictscore
#10
#20
#30
Test results
testverdicttimegroup
#1--1, 2, 3details
#2--2, 3details
#3--3details

### 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) 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)
{
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;
return c;
}```

### Test details

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)

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)