| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 645529 |
2022-09-27T09:51:43 Z |
Vanilla |
Paths (RMI21_paths) |
C++17 |
|
350 ms |
20588 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long int64;
typedef pair <int64, int64> pii;
const int maxn = 1e3 + 2;
vector <int> ad [maxn];
vector <pii> lv;
int64 cost [maxn][maxn];
int dad [maxn];
int leaves = 0;
const int64 maxn1 = 1e5 + 2;
vector <int> ad1 [maxn];
map <pair <int, int>, int> cost1;
int64 dp [maxn1];
void prec (int u, int p, int64 sum) {
bool f = 0;
for (int v: ad[u]) {
if (v == p) continue;
f = 1;
dad[v] = u;
prec(v, u, sum + cost[u][v]);
}
if (!f) lv.push_back({sum, u});
}
void dfs1 (int u, int p) {
// cerr << u << " ";
for (int v: ad1[u]) {
if (v == p) continue;
dfs1(v, u);
dp[u] = max(dp[u], dp[v] + cost1[{u, v}]);
}
}
void dfs2 (int u, int p, int64 sf) {
dp[u] = max(dp[u], sf);
vector <int> nd;
for (int v: ad1[u]) {
if (v == p) continue;
nd.push_back(v);
}
int m = nd.size();
vector <int64> pref(m), suff(m);
if (m) {
pref[0] = dp[nd[0]];
suff[m-1] = dp[nd[m-1]];
for (int i = 1; i < m; i++){
pref[i] = max(pref[i-1], dp[nd[i]] + cost1[{u, nd[i]}]);
}
for (int i = m - 2; i >= 0; i--){
suff[i] = max(suff[i + 1], dp[nd[i]] + cost1[{u, nd[i]}]);
}
for (int i = 0; i < m; i++){
int64 p1 = (i ? pref[i-1]: 0);
int64 p2 = ((i != m - 1) ? suff[i + 1]: 0);
dfs2(nd[i], u, max({p1, p2, sf}) + cost1[{u, nd[i]}]);
}
}
}
int main() {
int n,k;
cin >> n >> k;
if (k == 1) {
for (int i = 0; i < n - 1; i++){
int a,b,c;
cin >> a >> b >> c;
ad1[a].push_back(b);
ad1[b].push_back(a);
cost1[{a,b}] = cost1[{b, a}] = c;
}
dfs1(1, -1);
dfs2(1, -1, 0);
for (int i = 1; i <= n; i++){
// cout << i << ": ";
cout << dp[i] << "\n";
}
}
else {
for (int i = 0; i < n - 1; i++){
int a,b,c;
cin >> a >> b >> c;
cost[a][b] = cost[b][a] = c;
ad[a].push_back(b);
ad[b].push_back(a);
}
for (int i = 1; i <= n; i++){
if (ad[i].size() == 1) leaves++;
}
if (ad[1].size() == 1) leaves--;
for (int i = 1; i <= n; i++){
// k = min(k, leaves);
int64 rs = 0;
vector <pair <pii, int> > back;
for (int j = 0; j < k; j++){
lv.clear();
prec(i, -1, 0);
dad[i] = -1;
sort(lv.rbegin(), lv.rend());
cout << i << " " << j << " " << lv[0].first << " " << lv[0].second << "\n";
rs+=lv[0].first;
int k = lv[0].second;
while (k != i) {
int p = dad[k];
if (cost[p][k]) back.push_back({{p, k}, cost[p][k]});
cost[p][k] = 0;
k = p;
}
}
for (auto [x, y]: back) {
cost[x.first][x.second] = y;
}
// cout << i << ": ";
cout << rs << "\n";
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
350 ms |
20588 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
