oj.uz

Submission #645916

# Submission time Handle Problem Language Result Execution time Memory
645916 2022-09-28T09:21:00 Z TimDee Paths (RMI21_paths) C++17
36 / 100
 600 ms 9316 KB 
#include <bits/stdc++.h>
using namespace std;

//#pragma GCC optimize("O3")
//#pragma GCC optimize("Ofast")

#define int long long
#define forn(i,n) for (int i=0; i<n; ++i)
#define pi pair<int,int>
#define pb(x) push_back(x)
#define f first
#define s second

vector<vector<pi>> adj(1e5+1);
int n,k;
vector<int> d;
vector<int> par;
int R;
unordered_map<int,unordered_map<int,int>> m;

void dfs(int u, int p) {
	for (auto x:adj[u]) {
		int v=x.f;
		if (v==p) continue;
		par[v]=u;
		d[v]=d[u]+x.s;
		dfs(v,u);
	}
}

void setd(int u) {
	for (auto x:adj[u]) {
		int v=x.f;
		if (v==par[u]) continue;
		d[v]=d[u]+x.s;
		setd(v);
	}
}

void climb(int u) {
	if (u==R) return;
	if (m[par[u]][u]) return;
	m[par[u]][u]=1;
	d[u]=0;
	for (auto x:adj[u]) {
		int v=x.f;
		if (v==par[u]) continue;
		if (m[u][v]) continue;
		d[v]=d[u]+x.s;
		setd(v);
	}
	climb(par[u]);
}

void root(int u) {
	R=u;
	d.assign(n+1,0);
	par.assign(n+1,0);
	m.clear();
	int ans=0;
	dfs(u,0);
	forn(i,k) {
		int mx=R;
		forn(j,n) {
			if (d[j+1]>d[mx]) mx=j+1;
		}
		ans+=d[mx];
		if (d[mx]==0) break;
		climb(mx);
	}
	cout<<ans<<'\n';
}

void solve() {
	
	cin>>n>>k;

	forn(i,n-1) {
		int u,v,x; cin>>u>>v>>x;
		adj[u].push_back({v,x});
		adj[v].push_back({u,x});
	}

	forn(i,n) root(i+1);

}

int32_t main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	solve();
	return 0;
}

Subtask #1
8.0 / 8.0

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

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 8 ms 2712 KB Output is correct
4 Correct 10 ms 2644 KB Output is correct
5 Correct 7 ms 2644 KB Output is correct
6 Correct 11 ms 2644 KB Output is correct
7 Correct 9 ms 2644 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 8 ms 2712 KB Output is correct
4 Correct 10 ms 2644 KB Output is correct
5 Correct 7 ms 2644 KB Output is correct
6 Correct 11 ms 2644 KB Output is correct
7 Correct 9 ms 2644 KB Output is correct
8 Correct 251 ms 2836 KB Output is correct
9 Correct 269 ms 2976 KB Output is correct
10 Correct 271 ms 2952 KB Output is correct
11 Correct 206 ms 2824 KB Output is correct
12 Correct 202 ms 2860 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 8 ms 2712 KB Output is correct
4 Correct 10 ms 2644 KB Output is correct
5 Correct 7 ms 2644 KB Output is correct
6 Correct 11 ms 2644 KB Output is correct
7 Correct 9 ms 2644 KB Output is correct
8 Correct 251 ms 2836 KB Output is correct
9 Correct 269 ms 2976 KB Output is correct
10 Correct 271 ms 2952 KB Output is correct
11 Correct 206 ms 2824 KB Output is correct
12 Correct 202 ms 2860 KB Output is correct
13 Execution timed out 1092 ms 3080 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1096 ms 9316 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 8 ms 2712 KB Output is correct
4 Correct 10 ms 2644 KB Output is correct
5 Correct 7 ms 2644 KB Output is correct
6 Correct 11 ms 2644 KB Output is correct
7 Correct 9 ms 2644 KB Output is correct
8 Correct 251 ms 2836 KB Output is correct
9 Correct 269 ms 2976 KB Output is correct
10 Correct 271 ms 2952 KB Output is correct
11 Correct 206 ms 2824 KB Output is correct
12 Correct 202 ms 2860 KB Output is correct
13 Execution timed out 1092 ms 3080 KB Time limit exceeded
14 Halted 0 ms 0 KB -