Submission #891237

#	Time	Username	Problem	Language	Result	Execution time	Memory
891237		fanwen	Paths (RMI21_paths)	C++17	56 / 100	1028 ms	15704 KiB

Main

#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 (stderr)

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 / 8
• Subtask 2: 11 / 11
• Subtask 3: 17 / 17
• Subtask 4: 20 / 20
• Subtask 5: 0 / 12
• Subtask 6: 0 / 32