oj.uz

Submission #891237

# Submission time Handle Problem Language Result Execution time Memory
891237 2023-12-22T14:42:50 Z fanwen Paths (RMI21_paths) C++17
56 / 100
 600 ms 15704 KB 
#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define ll long long
#define file(name)                  \
    if(fopen(name".inp", "r"))      \
        freopen(name".inp", "r", stdin), freopen(name".out", "w", stdout); 

const int MAX = 3e5 + 5;

int n, k;
long long dp[MAX];
vector <pair <int, int>> adj[MAX];

void dfs(int u, int p, vector <long long> &res) {
	for (pair <int, int> tmp : adj[u]) if(tmp.fi != p) {
		int v = tmp.fi, w = tmp.se;
		dfs(v, u, res);
		dp[u] = max(dp[u], dp[v] + w);
	}

	bool oke = false;
	for (pair <int, int> tmp : adj[u]) if(tmp.fi != p) {
		int v = tmp.fi, w = tmp.se;
		if(dp[u] != dp[v] + w || oke) res.emplace_back(dp[v] + w);
		else oke = true;
	}
}

void you_make_it(void) {
    cin >> n >> k;
    for (int i = 1; i < n; ++i) {
    	int u, v, w; cin >> u >> v >> w;
    	adj[u].emplace_back(v, w);
    	adj[v].emplace_back(u, w);
    }

    for (int i = 1; i <= n; ++i) {
    	fill(dp + 1, dp + n + 1, 0);
    	vector <long long> res;
    	dfs(i, 0, res);
    	res.push_back(dp[i]);
    	sort(res.begin(), res.end(), greater <long long>());
    	long long sum = 0;
    	for (int j = 0; j < min((int) res.size(), k); ++j) sum += res[j];
    	cout << sum << '\n';
    }
}

signed main() {

#ifdef LOCAL
    freopen("TASK.inp", "r", stdin);
    freopen("TASK.out", "w", stdout);
#endif
    file("paths");
    auto start_time = chrono::steady_clock::now();

    cin.tie(0), cout.tie(0) -> sync_with_stdio(0);

    you_make_it();

    auto end_time = chrono::steady_clock::now();

    cerr << "\nExecution time : " << chrono::duration_cast <chrono::milliseconds> (end_time - start_time).count() << "[ms]" << endl;

    return (0 ^ 0);
}

// Dream it. Wish it. Do it.

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:10:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 |         freopen(name".inp", "r", stdin), freopen(name".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:59:5: note: in expansion of macro 'file'
   59 |     file("paths");
      |     ^~~~
Main.cpp:10:49: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 |         freopen(name".inp", "r", stdin), freopen(name".out", "w", stdout);
      |                                          ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:59:5: note: in expansion of macro 'file'
   59 |     file("paths");
      |     ^~~~

Subtask #1
8.0 / 8.0

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

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8796 KB Output is correct
2 Correct 2 ms 8796 KB Output is correct
3 Correct 3 ms 8796 KB Output is correct
4 Correct 3 ms 8796 KB Output is correct
5 Correct 3 ms 8796 KB Output is correct
6 Correct 3 ms 8796 KB Output is correct
7 Correct 3 ms 8796 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8796 KB Output is correct
2 Correct 2 ms 8796 KB Output is correct
3 Correct 3 ms 8796 KB Output is correct
4 Correct 3 ms 8796 KB Output is correct
5 Correct 3 ms 8796 KB Output is correct
6 Correct 3 ms 8796 KB Output is correct
7 Correct 3 ms 8796 KB Output is correct
8 Correct 33 ms 8796 KB Output is correct
9 Correct 27 ms 8796 KB Output is correct
10 Correct 22 ms 9052 KB Output is correct
11 Correct 33 ms 8916 KB Output is correct
12 Correct 21 ms 8796 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8796 KB Output is correct
2 Correct 2 ms 8796 KB Output is correct
3 Correct 3 ms 8796 KB Output is correct
4 Correct 3 ms 8796 KB Output is correct
5 Correct 3 ms 8796 KB Output is correct
6 Correct 3 ms 8796 KB Output is correct
7 Correct 3 ms 8796 KB Output is correct
8 Correct 33 ms 8796 KB Output is correct
9 Correct 27 ms 8796 KB Output is correct
10 Correct 22 ms 9052 KB Output is correct
11 Correct 33 ms 8916 KB Output is correct
12 Correct 21 ms 8796 KB Output is correct
13 Correct 159 ms 8984 KB Output is correct
14 Correct 142 ms 9068 KB Output is correct
15 Correct 66 ms 9008 KB Output is correct
16 Correct 159 ms 8988 KB Output is correct
17 Correct 92 ms 8792 KB Output is correct
18 Correct 86 ms 8792 KB Output is correct
19 Correct 162 ms 8976 KB Output is correct

Subtask #5
0 / 12.0

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

Subtask #6
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8796 KB Output is correct
2 Correct 2 ms 8796 KB Output is correct
3 Correct 3 ms 8796 KB Output is correct
4 Correct 3 ms 8796 KB Output is correct
5 Correct 3 ms 8796 KB Output is correct
6 Correct 3 ms 8796 KB Output is correct
7 Correct 3 ms 8796 KB Output is correct
8 Correct 33 ms 8796 KB Output is correct
9 Correct 27 ms 8796 KB Output is correct
10 Correct 22 ms 9052 KB Output is correct
11 Correct 33 ms 8916 KB Output is correct
12 Correct 21 ms 8796 KB Output is correct
13 Correct 159 ms 8984 KB Output is correct
14 Correct 142 ms 9068 KB Output is correct
15 Correct 66 ms 9008 KB Output is correct
16 Correct 159 ms 8988 KB Output is correct
17 Correct 92 ms 8792 KB Output is correct
18 Correct 86 ms 8792 KB Output is correct
19 Correct 162 ms 8976 KB Output is correct
20 Execution timed out 1028 ms 15704 KB Time limit exceeded
21 Halted 0 ms 0 KB -