oj.uz

Submission #702712

# Submission time Handle Problem Language Result Execution time Memory
702712 2023-02-24T21:12:51 Z TimDee Paths (RMI21_paths) C++17
36 / 100
 600 ms 1120 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<int>> 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);
		int 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);
		int answer=0;
		forn(i,k) {
			answer-=*ans[u].begin();
			ans[u].erase(ans[u].begin());
		}
		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 1 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 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 10 ms 468 KB Output is correct
4 Correct 8 ms 468 KB Output is correct
5 Correct 8 ms 500 KB Output is correct
6 Correct 8 ms 492 KB Output is correct
7 Correct 9 ms 496 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 10 ms 468 KB Output is correct
4 Correct 8 ms 468 KB Output is correct
5 Correct 8 ms 500 KB Output is correct
6 Correct 8 ms 492 KB Output is correct
7 Correct 9 ms 496 KB Output is correct
8 Correct 328 ms 732 KB Output is correct
9 Correct 189 ms 852 KB Output is correct
10 Correct 247 ms 844 KB Output is correct
11 Correct 202 ms 648 KB Output is correct
12 Correct 274 ms 828 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 10 ms 468 KB Output is correct
4 Correct 8 ms 468 KB Output is correct
5 Correct 8 ms 500 KB Output is correct
6 Correct 8 ms 492 KB Output is correct
7 Correct 9 ms 496 KB Output is correct
8 Correct 328 ms 732 KB Output is correct
9 Correct 189 ms 852 KB Output is correct
10 Correct 247 ms 844 KB Output is correct
11 Correct 202 ms 648 KB Output is correct
12 Correct 274 ms 828 KB Output is correct
13 Execution timed out 1052 ms 1120 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 852 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 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 10 ms 468 KB Output is correct
4 Correct 8 ms 468 KB Output is correct
5 Correct 8 ms 500 KB Output is correct
6 Correct 8 ms 492 KB Output is correct
7 Correct 9 ms 496 KB Output is correct
8 Correct 328 ms 732 KB Output is correct
9 Correct 189 ms 852 KB Output is correct
10 Correct 247 ms 844 KB Output is correct
11 Correct 202 ms 648 KB Output is correct
12 Correct 274 ms 828 KB Output is correct
13 Execution timed out 1052 ms 1120 KB Time limit exceeded
14 Halted 0 ms 0 KB -