Submission #982617

#	Time	Username	Problem	Language	Result	Execution time	Memory
982617		vjudge1	도로 폐쇄 (APIO21_roads)	C++17	0 / 100	2064 ms	24976 KiB

roads

#include "roads.h"
#include <bits/stdc++.h>
#include <vector>
using namespace std;
vector<pair<int, int>> g[200001];
vector<long long> v;
int n, i, j;
long long dp[200001][2];

void dfs(int x, int pr, int k, int c) {
	for (auto y : g[x]) if (y.first != pr) dfs(y.first, x, k, y.second);
	vector<int> vv;
	for (auto y : g[x]) {
		if (y.first == pr) continue;
		dp[x][0] += dp[y.first][0];
	}
	dp[x][1] = dp[x][0];
	for (auto y : g[x]) {
		if (y.first == pr) continue;
		vv.push_back({-dp[y.first][0] + dp[y.first][1] + y.second});
	}
	sort(vv.begin(), vv.end());
	//int w = vv.size() * 52;
	int w = (int)vv.size() - k;
	for (int i = 0; i < min((int)vv.size(), w + 1); i++) {
		dp[x][0] += vv[i];
	}
	for (int i = 0; i < min((int)vv.size(), w); i++) {
		dp[x][1] += vv[i];
	}
	//cout << x << " " << dp[x][0] << " " << dp[x][1] << "\n";
}

std::vector<long long> minimum_closure_costs(int N, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
	n = N;
	for (int i = 0; i < N - 1; i++) {
		g[U[i]].push_back({V[i], W[i]});
		g[V[i]].push_back({U[i], W[i]});
	}
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) dp[j][0] = dp[j][1] = 0;
		dfs(0, 0, i, 0);
		v.push_back(dp[0][1]);
	}
  return v;
}

/*
 *
5
0 1 1
0 2 4
0 3 3
2 4 2

 * */

Compilation message (stderr)

roads.cpp: In function 'void dfs(int, int, int, int)':
roads.cpp:20:50: warning: narrowing conversion of '(((- dp[y.std::pair<int, int>::first][0]) + dp[y.std::pair<int, int>::first][1]) + ((long long int)y.std::pair<int, int>::second))' from 'long long int' to 'std::vector<int>::value_type' {aka 'int'} [-Wnarrowing]
   20 |   vv.push_back({-dp[y.first][0] + dp[y.first][1] + y.second});
      |                 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 7
• Subtask 3: 0 / 14
• Subtask 4: 0 / 10
• Subtask 5: 0 / 17
• Subtask 6: 0 / 25
• Subtask 7: 0 / 22