oj.uz

Submission #702714

# Submission time Handle Problem Language Result Execution time Memory
702714 2023-02-24T21:14:57 Z TimDee Paths (RMI21_paths) C++17
36 / 100
 600 ms 880 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 1 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 1 ms 468 KB Output is correct
3 Correct 7 ms 468 KB Output is correct
4 Correct 6 ms 468 KB Output is correct
5 Correct 6 ms 508 KB Output is correct
6 Correct 4 ms 488 KB Output is correct
7 Correct 5 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 1 ms 468 KB Output is correct
3 Correct 7 ms 468 KB Output is correct
4 Correct 6 ms 468 KB Output is correct
5 Correct 6 ms 508 KB Output is correct
6 Correct 4 ms 488 KB Output is correct
7 Correct 5 ms 468 KB Output is correct
8 Correct 214 ms 604 KB Output is correct
9 Correct 113 ms 600 KB Output is correct
10 Correct 78 ms 552 KB Output is correct
11 Correct 142 ms 584 KB Output is correct
12 Correct 107 ms 548 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 1 ms 468 KB Output is correct
3 Correct 7 ms 468 KB Output is correct
4 Correct 6 ms 468 KB Output is correct
5 Correct 6 ms 508 KB Output is correct
6 Correct 4 ms 488 KB Output is correct
7 Correct 5 ms 468 KB Output is correct
8 Correct 214 ms 604 KB Output is correct
9 Correct 113 ms 600 KB Output is correct
10 Correct 78 ms 552 KB Output is correct
11 Correct 142 ms 584 KB Output is correct
12 Correct 107 ms 548 KB Output is correct
13 Execution timed out 976 ms 880 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 1 ms 468 KB Output is correct
3 Correct 7 ms 468 KB Output is correct
4 Correct 6 ms 468 KB Output is correct
5 Correct 6 ms 508 KB Output is correct
6 Correct 4 ms 488 KB Output is correct
7 Correct 5 ms 468 KB Output is correct
8 Correct 214 ms 604 KB Output is correct
9 Correct 113 ms 600 KB Output is correct
10 Correct 78 ms 552 KB Output is correct
11 Correct 142 ms 584 KB Output is correct
12 Correct 107 ms 548 KB Output is correct
13 Execution timed out 976 ms 880 KB Time limit exceeded
14 Halted 0 ms 0 KB -