oj.uz

답안 #897798

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
897798 2024-01-03T17:11:23 Z denniskim Putovanje (COCI20_putovanje) C++17
110 / 110
 103 ms 43628 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef __int128 lll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pld;
#define MAX 9223372036854775807LL
#define MIN -9223372036854775807LL
#define INF 0x3f3f3f3f3f3f3f3f
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cout << fixed; cout.precision(10);
#define sp << " "
#define en << "\n"
#define compress(v) sort(v.begin(), v.end()), v.erase(unique(v.begin(), v.end()), v.end())

ll n;
vector< pair<pll, pll> > edg;
ll all, bll, cll, dll;
vector<pll> vec[200010];
ll Pnum[200010];
ll dep[200010], spa[200010][21];
ll nu[200010];
ll sum[200010];
ll ans;

void dfs(ll here, ll pa)
{
	spa[here][0] = pa;
	
	for(auto &i : vec[here])
	{
		if(i.fi == pa)
			continue;
		
		dep[i.fi] = dep[here] + 1;
		Pnum[i.fi] = i.se;
		dfs(i.fi, here);
	}
}

ll LCA(ll X, ll Y)
{
	if(dep[X] < dep[Y])
		swap(X, Y);
	
	ll cha = dep[X] - dep[Y];
	
	for(ll i = 20 ; i >= 0 ; i--)
	{
		if(cha >= (1LL << i))
		{
			cha -= (1LL << i);
			X = spa[X][i];
		}
	}
	
	if(X == Y)
		return X;
	
	for(ll i = 20 ; i >= 0 ; i--)
	{
		if(spa[X][i] != spa[Y][i])
		{
			X = spa[X][i];
			Y = spa[Y][i];
		}
	}
	
	return spa[X][0];
}

void dfs2(ll here, ll pa)
{
	for(auto &i : vec[here])
	{
		if(i.fi == pa)
			continue;
		
		dfs2(i.fi, here);
		nu[here] += nu[i.fi];
	}
	
	sum[Pnum[here]] += nu[here];
}

int main(void)
{
	fastio
	
	cin >> n;
	
	for(ll i = 1 ; i < n ; i++)
	{
		cin >> all >> bll >> cll >> dll;
		
		edg.push_back({{all, bll}, {cll, dll}});
		vec[all].push_back({bll, i - 1});
		vec[bll].push_back({all, i - 1});
	}
	
	dfs(1, 0);
	
	for(ll i = 1 ; i <= 20 ; i++)
	{
		for(ll j = 1 ; j <= n ; j++)
			spa[j][i] = spa[spa[j][i - 1]][i - 1];
	}
	
	for(ll i = 1 ; i < n ; i++)
	{
		nu[i]++, nu[i + 1]++;
		nu[LCA(i, i + 1)] -= 2;
	}
	
	dfs2(1, 0);
	
	for(ll i = 0 ; i < n - 1 ; i++)
		ans += min(sum[i] * edg[i].se.fi, edg[i].se.se);
	
	cout << ans;
	return 0;
}

Subtask #1
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 11100 KB Output is correct
2 Correct 3 ms 11356 KB Output is correct
3 Correct 3 ms 11356 KB Output is correct
4 Correct 3 ms 11392 KB Output is correct
5 Correct 4 ms 11356 KB Output is correct
6 Correct 2 ms 11300 KB Output is correct
7 Correct 2 ms 11356 KB Output is correct
8 Correct 3 ms 11292 KB Output is correct
9 Correct 3 ms 11440 KB Output is correct

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 83 ms 38484 KB Output is correct
2 Correct 96 ms 40572 KB Output is correct
3 Correct 83 ms 43628 KB Output is correct
4 Correct 103 ms 42936 KB Output is correct
5 Correct 2 ms 11352 KB Output is correct
6 Correct 99 ms 38524 KB Output is correct
7 Correct 54 ms 30860 KB Output is correct
8 Correct 75 ms 38532 KB Output is correct
9 Correct 73 ms 42232 KB Output is correct
10 Correct 54 ms 38704 KB Output is correct
11 Correct 71 ms 41896 KB Output is correct
12 Correct 66 ms 42676 KB Output is correct

Subtask #3
65.0 / 65.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 11100 KB Output is correct
2 Correct 3 ms 11356 KB Output is correct
3 Correct 3 ms 11356 KB Output is correct
4 Correct 3 ms 11392 KB Output is correct
5 Correct 4 ms 11356 KB Output is correct
6 Correct 2 ms 11300 KB Output is correct
7 Correct 2 ms 11356 KB Output is correct
8 Correct 3 ms 11292 KB Output is correct
9 Correct 3 ms 11440 KB Output is correct
10 Correct 83 ms 38484 KB Output is correct
11 Correct 96 ms 40572 KB Output is correct
12 Correct 83 ms 43628 KB Output is correct
13 Correct 103 ms 42936 KB Output is correct
14 Correct 2 ms 11352 KB Output is correct
15 Correct 99 ms 38524 KB Output is correct
16 Correct 54 ms 30860 KB Output is correct
17 Correct 75 ms 38532 KB Output is correct
18 Correct 73 ms 42232 KB Output is correct
19 Correct 54 ms 38704 KB Output is correct
20 Correct 71 ms 41896 KB Output is correct
21 Correct 66 ms 42676 KB Output is correct
22 Correct 78 ms 38796 KB Output is correct
23 Correct 64 ms 35844 KB Output is correct
24 Correct 103 ms 39012 KB Output is correct
25 Correct 3 ms 11352 KB Output is correct
26 Correct 37 ms 22124 KB Output is correct
27 Correct 60 ms 33404 KB Output is correct
28 Correct 58 ms 37816 KB Output is correct
29 Correct 76 ms 42760 KB Output is correct
30 Correct 65 ms 42168 KB Output is correct
31 Correct 3 ms 11356 KB Output is correct