oj.uz

Submission #645913

# Submission time Handle Problem Language Result Execution time Memory
645913 2022-09-28T09:13:57 Z TimDee Paths (RMI21_paths) C++17
19 / 100
 600 ms 22240 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]+(1-m[u][v])*x.s;
		dfs(v,u);
	}
}

void climb(int u) {
	if (u==R) return;
	m[par[u]][u]=1;
	climb(par[u]);
}

void root(int u) {
	R=u;
	d.assign(n+1,0);
	par.assign(n+1,0);
	m.clear();
	int ans=0;
	if (n>200) {
		dfs(u,0);
		return;
	}
	forn(i,k) {
		dfs(u,0);
		int mx=R;
		forn(j,n) {
			if (d[j+1]>d[mx]) mx=j+1;
		}
		ans+=d[mx];
		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 1 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 1 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 25 ms 2716 KB Output is correct
4 Correct 26 ms 2644 KB Output is correct
5 Correct 24 ms 2720 KB Output is correct
6 Correct 23 ms 2740 KB Output is correct
7 Correct 25 ms 2644 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 25 ms 2716 KB Output is correct
4 Correct 26 ms 2644 KB Output is correct
5 Correct 24 ms 2720 KB Output is correct
6 Correct 23 ms 2740 KB Output is correct
7 Correct 25 ms 2644 KB Output is correct
8 Incorrect 117 ms 2772 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 25 ms 2716 KB Output is correct
4 Correct 26 ms 2644 KB Output is correct
5 Correct 24 ms 2720 KB Output is correct
6 Correct 23 ms 2740 KB Output is correct
7 Correct 25 ms 2644 KB Output is correct
8 Incorrect 117 ms 2772 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

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

Subtask #6
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 25 ms 2716 KB Output is correct
4 Correct 26 ms 2644 KB Output is correct
5 Correct 24 ms 2720 KB Output is correct
6 Correct 23 ms 2740 KB Output is correct
7 Correct 25 ms 2644 KB Output is correct
8 Incorrect 117 ms 2772 KB Output isn't correct
9 Halted 0 ms 0 KB -