oj.uz

Submission #702715

# Submission time Handle Problem Language Result Execution time Memory
702715 2023-02-24T21:16:47 Z TimDee Paths (RMI21_paths) C++17
36 / 100
 600 ms 768 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<multiset<ll>> ans(n);

vector<int> d(n,0);
vector<int> paiuans(n,0);
void paiu() {

}

void dfs(int u,int p) {
	for(auto&e:adj[u]) {
		int v=e.f,w=e.s;
		if (v==p) continue;
		dfs(v,u);
		ll x=*ans[v].begin();
		ans[v].erase(ans[v].begin());
		ans[v].insert(x-w);
		if (ans[u].size()<ans[v].size()) swap(ans[u],ans[v]);
		for(auto&x:ans[v]) ans[u].insert(x);
	}
	if (!ans[u].size()) ans[u].insert(0);
}

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();
		dfs(u,-1);
		ll answer=0;
		forn(i,k) {
			answer-=*ans[u].begin();
			ans[u].erase(ans[u].begin());
			if (!ans[u].size()) break;
		}
		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 468 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 468 KB Output is correct
2 Correct 0 ms 468 KB Output is correct
3 Correct 6 ms 468 KB Output is correct
4 Correct 5 ms 468 KB Output is correct
5 Correct 6 ms 468 KB Output is correct
6 Correct 3 ms 468 KB Output is correct
7 Correct 6 ms 468 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 468 KB Output is correct
2 Correct 0 ms 468 KB Output is correct
3 Correct 6 ms 468 KB Output is correct
4 Correct 5 ms 468 KB Output is correct
5 Correct 6 ms 468 KB Output is correct
6 Correct 3 ms 468 KB Output is correct
7 Correct 6 ms 468 KB Output is correct
8 Correct 219 ms 604 KB Output is correct
9 Correct 114 ms 624 KB Output is correct
10 Correct 82 ms 528 KB Output is correct
11 Correct 150 ms 584 KB Output is correct
12 Correct 123 ms 468 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 468 KB Output is correct
2 Correct 0 ms 468 KB Output is correct
3 Correct 6 ms 468 KB Output is correct
4 Correct 5 ms 468 KB Output is correct
5 Correct 6 ms 468 KB Output is correct
6 Correct 3 ms 468 KB Output is correct
7 Correct 6 ms 468 KB Output is correct
8 Correct 219 ms 604 KB Output is correct
9 Correct 114 ms 624 KB Output is correct
10 Correct 82 ms 528 KB Output is correct
11 Correct 150 ms 584 KB Output is correct
12 Correct 123 ms 468 KB Output is correct
13 Execution timed out 970 ms 768 KB Time limit exceeded
14 Halted 0 ms 0 KB -

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 468 KB Output is correct
2 Correct 0 ms 468 KB Output is correct
3 Correct 6 ms 468 KB Output is correct
4 Correct 5 ms 468 KB Output is correct
5 Correct 6 ms 468 KB Output is correct
6 Correct 3 ms 468 KB Output is correct
7 Correct 6 ms 468 KB Output is correct
8 Correct 219 ms 604 KB Output is correct
9 Correct 114 ms 624 KB Output is correct
10 Correct 82 ms 528 KB Output is correct
11 Correct 150 ms 584 KB Output is correct
12 Correct 123 ms 468 KB Output is correct
13 Execution timed out 970 ms 768 KB Time limit exceeded
14 Halted 0 ms 0 KB -