oj.uz

답안 #1068028

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1068028 2024-08-21T06:46:31 Z 정민찬(#11128) Paths (RMI21_paths) C++17
12 / 100
 69 ms 12108 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;

const ll inf = 2e18;

vector<pll> adj[100010];

ll down[100010];
ll up[100010];
ll N, K;

void dfs1(ll x, ll p) {
	down[x] = 0;
	for (auto &[y, c] : adj[x]) {
		if (y == p) continue;
		dfs1(y, x);
		down[x] = max(down[x], down[y] + c);
	}
}

void dfs2(ll x, ll p) {
	ll mx1 = 0, mx2 = 0;
	for (auto &[y, c] : adj[x]) {
		if (y == p) continue;
		if (mx1 < down[y] + c) {
			mx2 = mx1; mx1 = down[y] + c;
		}
		else if (mx2 < down[y] + c) {
			mx2 = down[y] + c;
		}
	}
	for (auto &[y, c] : adj[x]) {
		if (y == p) continue;
		up[y] = up[x] + c;
		if (mx1 == down[y] + c) up[y] = max(up[y], mx2 + c);
		else up[y] = max(up[y], mx1 + c);
		dfs2(y, x);
	}
}

void case1() {
	dfs1(1, 0);
	dfs2(1, 0);
	for (ll i=1; i<=N; i++) {
		cout << max(up[i], down[i]) << '\n';
	}
}

void case2() {
	ll tot = 0;
	for (ll i=1; i<=N; i++) {
		for (auto &[j, c] : adj[i]) {
			if (i < j) tot += c;
		}
	}
	for (ll i=1; i<=N; i++) {
		cout << tot << '\n';
	}
}

ll dist1[100010], dist2[100010];
ll par[100010];

void dfs3(ll x, ll p) {
	for (auto &[y, c] : adj[x]) {
		if (y == p) continue;
		par[y] = x;
		dist1[y] = dist1[x] + c;
		dist2[y] = dist2[x] + 1;
		dfs3(y, x);
	}
}

ll in[100010], out[100010];
ll pv = 1;
ll inv[100010];
ll parc[100010];

void dfs4(ll x, ll p) {
	in[x] = pv;
	if (p && adj[x].size() == 1) {
		inv[pv] = x;
		pv ++;
	}
	for (auto &[y, c] : adj[x]) {
		if (y == p) continue;
		par[y] = x;
		parc[y] = c;
		dist1[y] = dist1[x] + c;
		dfs4(y, x);
	}
	out[x] = pv;
}

struct SegmentTree{
	vector<pll> tree;
	vector<ll> lazy;
	void init(ll n) {
		ll sz = 1 << __lg(n-1) + 2;
		tree.resize(sz);
		lazy.resize(sz);
		build(1, 1, n);
	}
	void build(ll node, ll s, ll e) {
		lazy[node] = 0;
		if (s == e) {
			tree[node] = {dist1[inv[s]], s};
			return;
		}
		ll mid = s + e >> 1;
		build(node*2, s, mid);
		build(node*2+1, mid+1, e);
		tree[node] = max(tree[node*2], tree[node*2+1]);
	}
	void propagate(ll node, ll s, ll e) {
		tree[node].first -= lazy[node];
		if (s != e) {
			lazy[node*2] += lazy[node];
			lazy[node*2+1] += lazy[node];
		}
		lazy[node] = 0;
	}
	void update(ll node, ll s, ll e, ll l, ll r, ll v) {
		propagate(node, s, e);
		if (l > e || s > r) return;
		if (l <= s && e <= r) {
			lazy[node] = v;
			propagate(node, s, e);
			return;
		}
		ll mid = s + e >> 1;
		update(node*2, s, mid, l, r, v);
		update(node*2+1, mid+1, e, l, r, v);
		tree[node] = max(tree[node*2], tree[node*2+1]);
	}
	void del(ll node, ll s, ll e, ll tar) {
		propagate(node, s, e);
		if (s > tar || tar > e) return;
		if (s == e) {
			tree[node] = {-inf, -1};
			return;
		}
		ll mid = s + e >> 1;
		del(node*2, s, mid, tar);
		del(node*2+1, mid+1, e, tar);
		tree[node] = max(tree[node*2], tree[node*2+1]);
	}
	pll query(ll node, ll s, ll e, ll l, ll r) {
		propagate(node, s, e);
		if (l > e || s > r) return {-inf, -1};
		if (l <= s && e <= r) return tree[node];
		ll mid = s + e >> 1;
		return max(query(node*2, s, mid, l, r), query(node*2+1, mid+1, e, l, r));
	}
};

SegmentTree seg;
ll vis[100010];

void Ers(ll x) {
	while (x && !vis[x]) {
		seg.update(1, 1, pv-1, in[x], out[x]-1, parc[x]);
		vis[x] = 1;
		x = par[x];
	}
}

ll ans[100010];

void dfs5(ll x, ll p) {
	for (auto &[y, c] : adj[x]) {
		if (y == p) continue;
		if (vis[y]) ans[y] = ans[x];
		else ans[y] = ans[x] + c;
		dfs5(y, x);
	}
}

void solve(ll mid, ll r1, ll r2) {
	if (adj[mid].size() == 1) return;
	//cout << mid << '\n';
	memset(vis, 0, sizeof(vis));
	par[mid] = 0;
	parc[mid] = 0;
   	dist1[mid] = 0;
   	pv = 1;
   	dfs4(mid, 0);
   	seg.init(pv - 1);
   	ll sum = dist1[r1] + dist1[r2];
   	assert(seg.tree[1].first == max(dist1[r1], dist1[r2]));
   	seg.del(1, 1, pv-1, in[r1]);
   	Ers(r1);
   	if (seg.tree[1].first != min(dist1[r1], dist1[r2])) return;
   	seg.del(1, 1, pv-1, in[r2]);
   	Ers(r2);
   	vector<ll> ch = {r1, r2};
   	for (ll rep=0; rep<K-2; rep++) {
   		ll id = seg.tree[1].second;
   		sum += seg.tree[1].first;
   		seg.del(1, 1, pv-1, id);
   		Ers(inv[id]);
   		ch.push_back(inv[id]);
   	}
   	ans[mid] = sum;
   	dfs5(mid, 0);
   	if (seg.tree[1].second != -1) {
   		sum += seg.tree[1].first;
   		for (auto &i : ch) {
   			ans[i] = sum;
   		}
   	}
   	for (ll i=1; i<=N; i++) {
   		cout << ans[i] << '\n';
   	}
   	exit(0);
}

int main() {
    ios_base :: sync_with_stdio(false); cin.tie(NULL);
    cin >> N >> K;
    for (ll i=0; i<N-1; i++) {
    	ll u, v, c;
    	cin >> u >> v >> c;
    	adj[u].push_back({v, c});
    	adj[v].push_back({u, c});
    }
    if (K == 1) {
    	case1();
    	return 0;
    }
    ll leaf = 0;
    for (ll i=1; i<=N; i++) {
    	if (adj[i].size() <= 1)
    		leaf ++;
    }
    if (leaf <= K) {
    	case2();
    	return 0;
    }
    dist1[1] = dist2[1] = 0;
    dfs3(1, 0);
    pll mx = {-1, -1};
    ll r1 = -1;
    for (ll i=1; i<=N; i++) {
    	if (mx < pll{dist1[i], dist2[i]}) {
    		mx = {dist1[i], dist2[i]};
    		r1 = i;
    	}
    }
    dist1[r1] = dist2[r1] = 0;
    par[r1] = 0;
    dfs3(r1, 0);
    mx = {-1, -1}; ll r2 = -1;
    for (ll i=1; i<=N; i++) {
    	if (mx < pll{dist1[i], dist2[i]}) {
    		mx = {dist1[i], dist2[i]};
    		r2 = i;
    	}
    }
    assert(r1 != r2);
   	ll x = r2;
   	ll mid1 = -1, mid2 = -1;
   	while (x) {
   		pll d1 = {dist1[x], dist2[x]};
   		pll d2 = {dist1[r2] - dist1[x], dist2[r2] - dist2[x]};
   		if (d1 > d2) mid1 = x;
   		else {
   			mid2 = x;
   			break;
   		}
   		x = par[x];
   	}
   	solve(mid1, r1, r2);
   	solve(mid2, r1, r2);
   	assert(0);
   	//cout << mid << '\n';
   	
}

Compilation message

Main.cpp: In member function 'void SegmentTree::init(ll)':
Main.cpp:103:26: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
  103 |   ll sz = 1 << __lg(n-1) + 2;
      |                ~~~~~~~~~~^~~
Main.cpp: In member function 'void SegmentTree::build(ll, ll, ll)':
Main.cpp:114:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  114 |   ll mid = s + e >> 1;
      |            ~~^~~
Main.cpp: In member function 'void SegmentTree::update(ll, ll, ll, ll, ll, ll)':
Main.cpp:135:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  135 |   ll mid = s + e >> 1;
      |            ~~^~~
Main.cpp: In member function 'void SegmentTree::del(ll, ll, ll, ll)':
Main.cpp:147:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  147 |   ll mid = s + e >> 1;
      |            ~~^~~
Main.cpp: In member function 'pll SegmentTree::query(ll, ll, ll, ll, ll)':
Main.cpp:156:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  156 |   ll mid = s + e >> 1;
      |            ~~^~~

Subtask #1
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 3420 KB Output is correct
2 Runtime error 5 ms 7004 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 3420 KB Output is correct
2 Runtime error 5 ms 7004 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 3420 KB Output is correct
2 Runtime error 5 ms 7004 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 3420 KB Output is correct
2 Runtime error 5 ms 7004 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #5
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 43 ms 10448 KB Output is correct
2 Correct 41 ms 12108 KB Output is correct
3 Correct 69 ms 10320 KB Output is correct
4 Correct 43 ms 10448 KB Output is correct
5 Correct 43 ms 11088 KB Output is correct
6 Correct 64 ms 10436 KB Output is correct

Subtask #6
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 3420 KB Output is correct
2 Runtime error 5 ms 7004 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -