| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1111212 |
2024-11-11T17:36:44 Z |
vako_p |
Parkovi (COCI22_parkovi) |
C++14 |
|
3000 ms |
96668 KB |
#include <bits/stdc++.h>
using namespace std;
#define ll int
#define pb push_back
const int mxN = 1e6 + 5;
ll n,k,dis[mxN],mid;
vector<pair<int,int>> v[mxN];
vector<vector<ll>> vv[mxN];
bool vis[mxN];
void dfs(ll at, ll par){
for(auto it : v[at]){
if(it.first == par) continue;
dfs(it.first, at);
dis[at] = max(dis[at], dis[it.first] + it.second);
}
}
pair<ll,ll> dfs1(ll at, ll d, ll par, ll op){
bool ok = false;
if(dis[at] <= d) return {0, 0};
if(dis[at] <= mid){
if(op) vis[at] = true;
return {1, mid};
}
if(d < 0){
d = 0;
ok = true;
}
ll c1 = 1,d1 = d;
vv[at].clear();
for(auto it : v[at]){
if(it.first == par) continue;
auto x = dfs1(it.first, mid - it.second, at, 0).first;
c1 += x;
ll l = -1, r = mid;
while(r > l + 1){
ll mid1 = l + (r - l) / 2;
if(dfs1(it.first, mid1 - it.second, at, 0).first == x) r = mid1;
else l = mid1;
}
vv[at].pb({r, it.first, it.second});
}
sort(vv[at].begin(), vv[at].end());
for(auto it : vv[at]){
if(it[0] > d){
if(op) vis[at] = true;
if(op) for(auto it : v[at]){
if(it.first == par) continue;
dfs1(it.first, mid - it.second, at, 1);
}
return {c1, mid};
// cout << at << ' ' << d << ' ' << c1 << ' ' << mid << '\n';
}
else{
ll x = dfs1(it[1], d - it[2], at, 0).second - it[2];
if(x >= 0) ok = false;
d = max(d, x);
}
}
if(ok){
if(op) vis[at] = true;
if(op) for(auto it : v[at]){
if(it.first == par) continue;
dfs1(it.first, mid - it.second, at, 1);
}
return {c1, mid};
}
// cout << "--> " << at << ' ' << d1 << ' ' << c1 - 1 << ' ' << d << ' ' << mid << '\n';
if(op)for(auto it : vv[at]){
dfs1(it[1], d - it[2], at, 1);
}
return {c1 - 1, d};
}
bool ok(ll op){
return (dfs1(1, 0, 1, op).first <= k);
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> k;
for(int i = 0; i < n - 1; i++){
ll a,b,w;
cin >> a >> b >> w;
v[a].pb({b, w});
v[b].pb({a, w});
}
dfs(1, 1);
ll l = -1, r = 1e18;
while(r > l + 1){
mid = l + (r - l) / 2;
if(ok(0)) r = mid;
else l = mid;
}
cout << r << '\n';
mid = r;
ok(1);
ll cc = k;
for(int i = 1; i <= n; i++){
if(vis[i]){
cout << i << ' ';
cc--;
}
}
for(int i = 1; i <= n and cc > 0; i++){
if(!vis[i]){
cout << i << ' ';
cc--;
}
}
}
Compilation message
Main.cpp: In function 'std::pair<int, int> dfs1(int, int, int, int)':
Main.cpp:31:12: warning: unused variable 'd1' [-Wunused-variable]
31 | ll c1 = 1,d1 = d;
| ^~
Main.cpp: In function 'int main()':
Main.cpp:93:17: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
93 | ll l = -1, r = 1e18;
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
757 ms |
49488 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3060 ms |
96668 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
76 ms |
71064 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
757 ms |
49488 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
