oj.uz

Submission #702719

# Submission time Handle Problem Language Result Execution time Memory
702719 2023-02-24T22:36:08 Z TimDee Paths (RMI21_paths) C++17
56 / 100
 222 ms 22164 KB 
#include <bits/stdc++.h>
using namespace std;
 
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx2,popcnt")

using ll = long long;
#define int long long
#define forn(i,n) for(int i=0; i<(n); ++i)
#define pb push_back
#define pi pair<int,int>
#define f first
#define s second
#define vii(a,n) vector<int> a(n); forn(i,n) cin>>a[i];
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int inf = INT_MAX;
const int mod = 998244353;

int n=2e3,k;
vector<vector<pi>> adj(n);
vector<vector<ll>> ans(n);
vector<int> mx(n,-1);

vector<int> d(n,0);
vector<int> paiuans(n,0);
void dfspaiu(int u, int p) {
	for(auto&e:adj[u]) {
		int v=e.f,w=e.s;
		if (v==p) continue;
		dfspaiu(v,u);
		d[u]=max(d[u],d[v]+w);
	}
}
void paia(int u, int p, int out) {
	vector<int> pref(1,0);
	paiuans[u]=max(d[u],out);
	for(auto&e:adj[u]) {
		int v=e.f,w=e.s;
		if (v==p) {pref.pb(pref.back()); continue;}
		pref.pb(max(pref.back(),d[v]+w));
	}
	int suf=0;
	int sz=adj[u].size();
	for(int i=sz-1; i>=0; --i) {
		auto e=adj[u][i];
		int v=e.f,w=e.s;
		if (v==p) continue;
		//cout<<v<<' '<<w<<"  "<<pref[i]<<' '<<suf<<'\n';
		paia(v,u,max({pref[i],suf,out})+w);
		suf=max(suf,d[v]+w);
	}
}
void paiu() {
	dfspaiu(0,-1);
	paia(0,-1,0);
	forn(i,n) cout<<paiuans[i]<<'\n';
	exit(0);
}

void dfs(int u,int p) {
	int m=-1;
	for(auto&e:adj[u]) {
		int v=e.f,w=e.s;
		if (v==p) continue;
		dfs(v,u);
		if (ans[u].size()<ans[v].size()) swap(ans[u],ans[v]);
		if (mx[v]+w>m) {
			if (m!=-1) ans[u].pb(m);
			m=mx[v]+w;
		} else {
			ans[u].pb(mx[v]+w);
		}
		for(auto&x:ans[v]) ans[u].pb(x);
	}
	mx[u]=max(m,0ll);
}

void solve() {

	cin>>n>>k;
	forn(i,n-1) {
		int u,v,w; cin>>u>>v>>w; --u, --v;
		adj[u].pb({v,w});
		adj[v].pb({u,w});
	}
	if (k==1) paiu();
	forn(u,n) {
		forn(i,n) ans[i].clear();
		mx.assign(n,-1);
		dfs(u,-1);
		ll answer=mx[u];
		sort(rall(ans[u]));

		forn(i,min(k-1,(int)ans[u].size())) {
			answer+=ans[u][i];
		}
		cout<<answer<<'\n';
	}

}

int32_t main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int t=1;
    //cin>>t;
    while (t--) solve();
    return 0;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 468 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 468 KB Output is correct
3 Correct 2 ms 596 KB Output is correct
4 Correct 2 ms 596 KB Output is correct
5 Correct 3 ms 596 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 2 ms 596 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 468 KB Output is correct
3 Correct 2 ms 596 KB Output is correct
4 Correct 2 ms 596 KB Output is correct
5 Correct 3 ms 596 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 2 ms 596 KB Output is correct
8 Correct 50 ms 3496 KB Output is correct
9 Correct 37 ms 3700 KB Output is correct
10 Correct 29 ms 1236 KB Output is correct
11 Correct 46 ms 6820 KB Output is correct
12 Correct 29 ms 1896 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 468 KB Output is correct
3 Correct 2 ms 596 KB Output is correct
4 Correct 2 ms 596 KB Output is correct
5 Correct 3 ms 596 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 2 ms 596 KB Output is correct
8 Correct 50 ms 3496 KB Output is correct
9 Correct 37 ms 3700 KB Output is correct
10 Correct 29 ms 1236 KB Output is correct
11 Correct 46 ms 6820 KB Output is correct
12 Correct 29 ms 1896 KB Output is correct
13 Correct 222 ms 18848 KB Output is correct
14 Correct 179 ms 12752 KB Output is correct
15 Correct 108 ms 1996 KB Output is correct
16 Correct 206 ms 22164 KB Output is correct
17 Correct 139 ms 6376 KB Output is correct
18 Correct 110 ms 9980 KB Output is correct
19 Correct 216 ms 12796 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 724 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 468 KB Output is correct
3 Correct 2 ms 596 KB Output is correct
4 Correct 2 ms 596 KB Output is correct
5 Correct 3 ms 596 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 2 ms 596 KB Output is correct
8 Correct 50 ms 3496 KB Output is correct
9 Correct 37 ms 3700 KB Output is correct
10 Correct 29 ms 1236 KB Output is correct
11 Correct 46 ms 6820 KB Output is correct
12 Correct 29 ms 1896 KB Output is correct
13 Correct 222 ms 18848 KB Output is correct
14 Correct 179 ms 12752 KB Output is correct
15 Correct 108 ms 1996 KB Output is correct
16 Correct 206 ms 22164 KB Output is correct
17 Correct 139 ms 6376 KB Output is correct
18 Correct 110 ms 9980 KB Output is correct
19 Correct 216 ms 12796 KB Output is correct
20 Runtime error 1 ms 724 KB Execution killed with signal 11
21 Halted 0 ms 0 KB -