oj.uz

답안 #1068097

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1068097 2024-08-21T07:29:09 Z 정민찬(#11128) Paths (RMI21_paths) C++17
20 / 100
 40 ms 14800 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];

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);
	}
}

ll dfs6(ll x, ll p, ll k) {
	ll sub = 0;
	for (auto &[y, c] : adj[x]) {
		if (y == p) continue;
		if (!vis[y]) continue;
		sub += dfs6(y, x, k) + c;
	}
	ans[x] = max(ans[x], k - sub);
	return sub;
}

pll solve(ll mid) {
	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 = 0;
   	ll id = seg.tree[1].second;
	sum += seg.tree[1].first;
	seg.del(1, 1, pv-1, id);
	Ers(inv[id]);
	ll mx = seg.tree[1].first, mx2 = -1;
	ll nid;
	for (auto &[y, c] : adj[mid]) {
		if (in[y] <= id && id < out[y]) continue;
		pll ret = seg.query(1, 1, pv-1, in[y], out[y]-1);
		if (ret.first > mx2) {
			mx2 = ret.first;
			nid = ret.second;
		}
	}
	if (mx2 < mx) {
		return {id, seg.tree[1].second};
	}
	assert(mx2 == mx);
	sum += mx2;
	seg.del(1, 1, pv-1, nid);
	Ers(inv[nid]);
   	vector<ll> ch = {inv[id], inv[nid]};
   	for (ll rep=0; rep<K-2; rep++) {
   		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) {
   		id = seg.tree[1].second;
   		sum += seg.tree[1].first;
   		seg.del(1, 1, pv-1, id);
   		Ers(inv[id]);
   		dfs6(mid, 0, 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;
    }
    for (ll i=1; i<=N; i++) {
    	solve(i);
    }
    assert(0);
    ll mid;
    for (ll i=1; i<=N; i++) {
    	if (adj[i].size() >= 2) {
    		mid = i;
    		break;
    	}
    }
   	
}

Compilation message

Main.cpp: In member function 'void SegmentTree::init(ll)':
Main.cpp:93:26: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   93 |   ll sz = 1 << __lg(n-1) + 2;
      |                ~~~~~~~~~~^~~
Main.cpp: In member function 'void SegmentTree::build(ll, ll, ll)':
Main.cpp:104:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  104 |   ll mid = s + e >> 1;
      |            ~~^~~
Main.cpp: In member function 'void SegmentTree::update(ll, ll, ll, ll, ll, ll)':
Main.cpp:125:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  125 |   ll mid = s + e >> 1;
      |            ~~^~~
Main.cpp: In member function 'void SegmentTree::del(ll, ll, ll, ll)':
Main.cpp:137:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  137 |   ll mid = s + e >> 1;
      |            ~~^~~
Main.cpp: In member function 'pll SegmentTree::query(ll, ll, ll, ll, ll)':
Main.cpp:146:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  146 |   ll mid = s + e >> 1;
      |            ~~^~~
Main.cpp: In function 'int main()':
Main.cpp:263:8: warning: variable 'mid' set but not used [-Wunused-but-set-variable]
  263 |     ll mid;
      |        ^~~
Main.cpp: In function 'pll solve(ll)':
Main.cpp:138:6: warning: 'nid' may be used uninitialized in this function [-Wmaybe-uninitialized]
  138 |   del(node*2, s, mid, tar);
      |   ~~~^~~~~~~~~~~~~~~~~~~~~
Main.cpp:198:5: note: 'nid' was declared here
  198 |  ll nid;
      |     ^~~

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 11100 KB Output is correct
2 Correct 2 ms 11100 KB Output is correct

Subtask #2
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 11100 KB Output is correct
2 Correct 2 ms 11100 KB Output is correct
3 Incorrect 2 ms 11352 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 11100 KB Output is correct
2 Correct 2 ms 11100 KB Output is correct
3 Incorrect 2 ms 11352 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 11100 KB Output is correct
2 Correct 2 ms 11100 KB Output is correct
3 Incorrect 2 ms 11352 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 37 ms 13392 KB Output is correct
2 Correct 40 ms 14800 KB Output is correct
3 Correct 34 ms 13088 KB Output is correct
4 Correct 35 ms 13260 KB Output is correct
5 Correct 37 ms 13916 KB Output is correct
6 Correct 38 ms 13004 KB Output is correct

Subtask #6
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 11100 KB Output is correct
2 Correct 2 ms 11100 KB Output is correct
3 Incorrect 2 ms 11352 KB Output isn't correct
4 Halted 0 ms 0 KB -