| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 786417 |
2023-07-18T07:36:33 Z |
박상훈(#10027) |
Paths (RMI21_paths) |
C++17 |
|
600 ms |
11696 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr int INF1 = 1e9 + 100;
constexpr ll INF2 = 4e18;
struct Node{
int x, p;
ll d;
Node(){}
Node(int _x, int _p, ll _d): x(_x), p(_p), d(_d) {}
bool operator < (const Node &N) const{
if (d==N.d) return p < N.p;
return d < N.d;
}
};
int n, k;
vector<pair<int, ll>> adj[100100];
ll dp1[100100], dp2[100100], D[100100], dist[100100];
int dp1_idx[100100], par[100100], T[100100];
int valP[100100], col[100100], on[100100], onS[100100];
ll ret1, ret2, onD[100100];
ll ans[100100];
void dfs1(int s, int pa = 0, ll paW = 0, int paT = 0){
dist[s] = paW;
dp1[s] = 0;
dp1_idx[s] = s;
par[s] = pa;
T[s] = paT;
for (auto &[v, w]:adj[s]) if (v!=pa){
dfs1(v, s, paW + w, (paT?paT:v));
if (dp1[s] < dp1[v] + w){
dp1[s] = dp1[v] + w;
dp1_idx[s] = dp1_idx[v];
}
}
}
void dfs2(int s, int pa = 0){
vector<pair<ll, int>> C;
D[s] = max(dp1[s], dp2[s]);
if (pa) C.emplace_back(dp2[s], s);
for (auto &[v, w]:adj[s]) if (v!=pa){
C.emplace_back(dp1[v] + w, v);
}
if (!C.empty()) swap(C[0], *max_element(C.begin(), C.end()));
if (C.size() > 1) swap(C[1], *max_element(C.begin()+1, C.end()));
for (auto &[v, w]:adj[s]) if (v!=pa){
if (C[0].second!=v) dp2[v] = C[0].first + w;
else if (C.size()==1) dp2[v] = w;
else dp2[v] = C[1].first + w;
dfs2(v, s);
}
}
void run(int root, vector<int> P){ // should call dfs1(root) first
ret1 = 0;
ret2 = 0;
fill(valP+1, valP+n+1, 0);
fill(col+1, col+n+1, 0);
fill(on+1, on+n+1, 0);
for (int i=0;i<(int)P.size();i++) valP[P[i]] = (int)P.size() - i;
priority_queue<Node> pq;
pq.emplace(dp1_idx[root], valP[dp1_idx[root]], dist[dp1_idx[root]]);
for (int z=1;z<=k;z++) if (!pq.empty()){
auto [x, _, d] = pq.top(); pq.pop();
on[x] = 1;
if (z <= (int)P.size()) assert(_ == (int)P.size() - z + 1);
ret1 += d;
while(true){
for (auto &[y, w]:adj[x]) if (y!=par[x] && !col[y]){
int z = dp1_idx[y];
pq.emplace(z, valP[z], dist[z] - dist[x]);
}
if (par[x] && !col[x]){
col[x] = 1;
x = par[x];
}
else break;
}
}
if (!pq.empty()) ret2 = pq.top().d;
}
void dfs3(int s, int pa = 0){
onS[s] = on[s];
if (on[s]) onD[s] = 0;
else onD[s] = INF2;
for (auto &[v, w]:adj[s]) if (v!=pa){
dfs3(v, s);
onS[s] += onS[v];
onD[s] = min(onD[s], onD[v] + w);
}
}
void get_optimal(int root){
dfs1(root);
vector<pair<ll, int>> C;
for (auto &[v, w]:adj[root]) C.emplace_back(dp1[v]+w, v);
assert(C.size() > 1);
swap(C[0], *max_element(C.begin(), C.end()));
swap(C[1], *max_element(C.begin()+1, C.end()));
vector<int> V(2);
for (int i=1;i<=n;i++) if (i!=root){
if (dist[i]==C[0].first && T[i]==C[0].second) V[0] = i;
if (dist[i]==C[1].first && T[i]==C[1].second) V[1] = i;
}
assert(V[0] && V[1]);
run(root, V);
dfs3(root);
}
void dfs4(int s, ll val, int pa = 0, int flag = 0){
ans[s] = val;
for (auto &[v, w]:adj[s]) if (v!=pa){
if (!col[v] || flag){
dfs4(v, val+w, s, flag);
}
else if (onS[v]==1 && val-onD[v]+ret2 > val){
dfs4(v, val-onD[v]+ret2, s, 1);
}
else{
dfs4(v, val, s, 0);
}
}
}
void naive(){
for (int i=1;i<=n;i++){
dfs1(i);
run(i, vector<int>());
printf("%lld\n", ret1);
}
}
int main(){
scanf("%d %d", &n, &k);
for (int i=1;i<=n-1;i++){
int x, y, z;
scanf("%d %d %d", &x, &y, &z);
adj[x].emplace_back(y, z);
adj[y].emplace_back(x, z);
}
naive();
return 0;
dfs1(1);
dfs2(1);
if (k==1){
for (int i=1;i<=n;i++){
printf("%lld\n", D[i]);
}
return 0;
}
if (n==2){
for (int i=1;i<=n;i++) printf("%lld\n", adj[1][0].second);
return 0;
}
int root = -1;
ll valD = INF2;
for (int i=1;i<=n;i++) if (D[i] < valD && adj[i].size() > 1){
valD = D[i];
root = i;
}
assert(root!=-1);
get_optimal(root);
dfs4(root, ret1);
for (int i=1;i<=n;i++){
printf("%lld\n", ans[i]);
}
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:164:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
164 | scanf("%d %d", &n, &k);
| ~~~~~^~~~~~~~~~~~~~~~~
Main.cpp:168:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
168 | scanf("%d %d %d", &x, &y, &z);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1047 ms |
11696 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
