oj.uz

Submission #1068099

# Submission time Handle Problem Language Result Execution time Memory
1068099 2024-08-21T07:32:12 Z 정민찬(#11128) Paths (RMI21_paths) C++17
48 / 100
 600 ms 14928 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;
}

ll 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;
   	for (ll rep=0; rep<K; rep++) {
   		ll id = seg.tree[1].second;
   		sum += seg.tree[1].first;
   		seg.del(1, 1, pv-1, id);
   		Ers(inv[id]);
   	}
   	return sum;
}

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++) {
    	cout << solve(i) << '\n';
    }
   	
}

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;
      |            ~~^~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 11096 KB Output is correct
2 Correct 1 ms 9052 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 11096 KB Output is correct
2 Correct 1 ms 9052 KB Output is correct
3 Correct 7 ms 9052 KB Output is correct
4 Correct 8 ms 4956 KB Output is correct
5 Correct 6 ms 3676 KB Output is correct
6 Correct 7 ms 4956 KB Output is correct
7 Correct 7 ms 11276 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 11096 KB Output is correct
2 Correct 1 ms 9052 KB Output is correct
3 Correct 7 ms 9052 KB Output is correct
4 Correct 8 ms 4956 KB Output is correct
5 Correct 6 ms 3676 KB Output is correct
6 Correct 7 ms 4956 KB Output is correct
7 Correct 7 ms 11276 KB Output is correct
8 Correct 107 ms 9308 KB Output is correct
9 Correct 148 ms 11356 KB Output is correct
10 Correct 106 ms 11100 KB Output is correct
11 Correct 64 ms 11356 KB Output is correct
12 Correct 95 ms 11324 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 11096 KB Output is correct
2 Correct 1 ms 9052 KB Output is correct
3 Correct 7 ms 9052 KB Output is correct
4 Correct 8 ms 4956 KB Output is correct
5 Correct 6 ms 3676 KB Output is correct
6 Correct 7 ms 4956 KB Output is correct
7 Correct 7 ms 11276 KB Output is correct
8 Correct 107 ms 9308 KB Output is correct
9 Correct 148 ms 11356 KB Output is correct
10 Correct 106 ms 11100 KB Output is correct
11 Correct 64 ms 11356 KB Output is correct
12 Correct 95 ms 11324 KB Output is correct
13 Execution timed out 795 ms 11356 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 13396 KB Output is correct
2 Correct 43 ms 14928 KB Output is correct
3 Correct 41 ms 13148 KB Output is correct
4 Correct 35 ms 13260 KB Output is correct
5 Correct 39 ms 13904 KB Output is correct
6 Correct 34 ms 13000 KB Output is correct

Subtask #6
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 11096 KB Output is correct
2 Correct 1 ms 9052 KB Output is correct
3 Correct 7 ms 9052 KB Output is correct
4 Correct 8 ms 4956 KB Output is correct
5 Correct 6 ms 3676 KB Output is correct
6 Correct 7 ms 4956 KB Output is correct
7 Correct 7 ms 11276 KB Output is correct
8 Correct 107 ms 9308 KB Output is correct
9 Correct 148 ms 11356 KB Output is correct
10 Correct 106 ms 11100 KB Output is correct
11 Correct 64 ms 11356 KB Output is correct
12 Correct 95 ms 11324 KB Output is correct
13 Execution timed out 795 ms 11356 KB Time limit exceeded
14 Halted 0 ms 0 KB -