oj.uz

답안 #372715

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
372715 2021-03-01T11:01:44 Z hivakarami 구슬과 끈 (APIO14_beads) C++14
13 / 100
 11 ms 14444 KB 
#include<bits/stdc++.h>
 
using namespace std;
 
typedef long long int ll;
typedef long double ld;
#define f first
#define s second
 
const int N = 2e5 + 100;
const ll mod = 998244353;
const ll inf = 1e9 + 100;

ll dp[4][N], par[N], ans = 0, e[N];
vector<pair<ll, ll>> adj[N];
multiset<ll> st[N];
int n;


inline void upd(int u)
{
	dp[1][u] = dp[0][u];
	if(st[u].size())
	{
		ll w = *(st[u].rbegin());
		dp[1][u] += max(0ll, w + e[u]);
	}
}


void dfs(int u)
{
	for(auto it : adj[u])
	{
		int x = it.f;
		ll w = it.s;
		if(x != par[u])
		{
			par[x] = u;
			e[x] = w;
			dfs(x);
			dp[0][u] += dp[1][x];
			st[u].insert(dp[0][x] - dp[1][x] + e[x]);
		}
	}
	
	upd(u);
	
	//cout << u << ' ' << dp[1][u] << ' ' << dp[2][u] << endl;
}

inline void move_root(int x, int u, ll w)
{
	st[x].erase(dp[0][u]-dp[1][u]+w);
	dp[0][x] -= dp[1][u];
	e[x] = w;
	upd(x);
	
	e[u] = 0;
	dp[0][u] += dp[1][x];
	st[u].insert(dp[0][x]-dp[1][x]+e[x]);
	upd(u);
	
}



void DFS(int u)
{
	ans = max(ans, dp[0][u]);
	for(auto it : adj[u])
	{
		int x = it.f;
		ll w = it.s;
		if(x == par[u])
			continue;
		move_root(u, x, w);
		DFS(x);
		move_root(x, u, w);
	
	}
}





int main()
{
    ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);	
	
	cin >> n;
	for(int i = 0; i < n-1; i++)
	{
		int x, y;
		ll w;
		cin >> x >> y >> w;
		x--; y--;
		adj[x].push_back({y, w});
		adj[y].push_back({x, w});
	}
	
	
	dfs(0);
	
	DFS(0);
		
	cout << ans << endl;
	
	
		
		
	return 0;
}

Subtask #1
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 14444 KB Output is correct
2 Correct 10 ms 14444 KB Output is correct
3 Correct 10 ms 14444 KB Output is correct
4 Correct 10 ms 14444 KB Output is correct
5 Correct 10 ms 14444 KB Output is correct
6 Correct 10 ms 14444 KB Output is correct
7 Correct 10 ms 14444 KB Output is correct
8 Correct 10 ms 14444 KB Output is correct
9 Correct 10 ms 14444 KB Output is correct
10 Correct 10 ms 14444 KB Output is correct
11 Correct 11 ms 14444 KB Output is correct
12 Correct 10 ms 14444 KB Output is correct

Subtask #2
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 14444 KB Output is correct
2 Correct 10 ms 14444 KB Output is correct
3 Correct 10 ms 14444 KB Output is correct
4 Correct 10 ms 14444 KB Output is correct
5 Correct 10 ms 14444 KB Output is correct
6 Correct 10 ms 14444 KB Output is correct
7 Correct 10 ms 14444 KB Output is correct
8 Correct 10 ms 14444 KB Output is correct
9 Correct 10 ms 14444 KB Output is correct
10 Correct 10 ms 14444 KB Output is correct
11 Correct 11 ms 14444 KB Output is correct
12 Correct 10 ms 14444 KB Output is correct
13 Correct 10 ms 14444 KB Output is correct
14 Incorrect 10 ms 14444 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 14444 KB Output is correct
2 Correct 10 ms 14444 KB Output is correct
3 Correct 10 ms 14444 KB Output is correct
4 Correct 10 ms 14444 KB Output is correct
5 Correct 10 ms 14444 KB Output is correct
6 Correct 10 ms 14444 KB Output is correct
7 Correct 10 ms 14444 KB Output is correct
8 Correct 10 ms 14444 KB Output is correct
9 Correct 10 ms 14444 KB Output is correct
10 Correct 10 ms 14444 KB Output is correct
11 Correct 11 ms 14444 KB Output is correct
12 Correct 10 ms 14444 KB Output is correct
13 Correct 10 ms 14444 KB Output is correct
14 Incorrect 10 ms 14444 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #4
0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 14444 KB Output is correct
2 Correct 10 ms 14444 KB Output is correct
3 Correct 10 ms 14444 KB Output is correct
4 Correct 10 ms 14444 KB Output is correct
5 Correct 10 ms 14444 KB Output is correct
6 Correct 10 ms 14444 KB Output is correct
7 Correct 10 ms 14444 KB Output is correct
8 Correct 10 ms 14444 KB Output is correct
9 Correct 10 ms 14444 KB Output is correct
10 Correct 10 ms 14444 KB Output is correct
11 Correct 11 ms 14444 KB Output is correct
12 Correct 10 ms 14444 KB Output is correct
13 Correct 10 ms 14444 KB Output is correct
14 Incorrect 10 ms 14444 KB Output isn't correct
15 Halted 0 ms 0 KB -