| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1225519 | Dreamy_lovesper | Parkovi (COCI22_parkovi) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
// Do you think you'll ever remember me someday, or will I just fade away from your memory?
#define LIFESUCK ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define ll long long
#define str string
#define mll map<ll, ll>
#define vll vector<ll>
#define pll pair<ll, ll>
#define fi first
#define se second
#define all(c) c.begin(), c.end()
#define pb push_back
#define debug cout << "I Love You\n";
#define fu(i, a, b) for (int i = a; i <= b; i++)
#define fd(i, b, a) for (int i = b; i >= a; i--)
#define Bitc(msk, j) ((msk >> j) & 1)
#define _log(x) 31 - __builtin_clz(x)
const ll Mod = 1e9 + 7;
const ll inf = (1ll << 30);
const ll lnf = (1ll << 60);
// When time passes and things change... will you still remember someone like me?
int64_t add(ll &a, ll b) {
a += b;
if (a >= Mod) a %= Mod;
while (a < 0) a += Mod;
return a;
}
int64_t mul(ll a, ll b) {
a = 1ll * a * b % Mod;
return a;
}
template <class X, class Y>
bool minimize(X &x, Y y) {
X eps = 1e-9;
if (x > y + eps) {
x = y;
return 1;
}
return 0;
}
template <class X, class Y>
bool maximize(X &x, Y y) {
X eps = 1e-9;
if (x + eps < y) {
x = y;
return 1;
}
return 0;
}
// I wonder… will I just become a distant memory to you one day?
#define mxn 200'007
ll n, k, g[mxn];
vector<pll> graph[mxn];
struct Edge {
ll u, v, w;
} edge[mxn];
namespace Love1 {
bool check () {
return (n <= 20);
}
struct EdgePrio {
ll d, u;
bool operator < ( const EdgePrio& other ) const {
return other.d > d;
}
};
ll f[27];
void DreamyLove () {
ll sad = lnf, gf;
fu(msk, 0, (1 << n) - 1) {
if(__builtin_popcount(msk) != k) continue;
priority_queue<EdgePrio> Q;
fu(i, 1, n) f[i] = lnf;
fu(j, 0, n - 1) if(Bitc(msk, j)) Q.push({0, j + 1}), f[j + 1] = 0;
ll cr = -lnf;
while(!Q.empty()) {
auto[d, u] = Q.top();Q.pop();
if ( d > f[u] ) continue;
for(pll& it: graph[u]){
ll v = it.fi, w = it.se;
if (f[v] <= f[u] + w) continue;
f[v] = f[u] + w;
Q.push({f[v], v});
}
}
fu(i, 1, n) maximize(cr, f[i]);
if(minimize(sad, cr)) gf = msk;
}
cout << sad << '\n';
fu (j, 0, n - 1 ) if (Bitc( gf, j)) cout << j + 1 << ' ';
//
}
}
namespace Love2 {
bool check () {
return (k == 1);
}
ll f[7][mxn];
struct EdgePrio {
ll d, u;
bool operator < ( const EdgePrio& other ) const {
return other.d > d;
}
};
void Dijkstra (ll s, ll* f) {
priority_queue<EdgePrio> Q;
Q.push({f[s] = 0, s});
while(!Q.empty()) {
auto[d, u] = Q.top();Q.pop();
if ( d > f[u] ) continue;
for(pll& it: graph[u]){
ll v = it.fi, w = it.se;
if (f[v] <= f[u] + w) continue;
f[v] = f[u] + w;
Q.push({f[v], v});
}
}
}
void DreamyLove () {
memset(f, 0x3f, sizeof(f));
Dijkstra(1, f[3]);
pll t = {0, 0};
fu(i, 1, n) if(maximize(t.se, f[3][i])) t.fi = i;
Dijkstra(t.fi, f[0]);
t = {0, 0};
fu(i, 1, n) if(maximize(t.se, f[0][i])) t.fi = i;
Dijkstra(t.fi, f[1]);
ll sad = 0, gf = lnf;
fu(i, 1, n) if(minimize(gf, max(f[0][i], f[1][i]))) sad = i;
cout << gf << '\n' << sad;
//
}
}
namespace Love3 {
bool check () {
ll cr = 0;
fu(i, 1, n) cr += (graph[i].size() == 1);
return (cr == 2);
}
ll g[mxn], pref[mxn];
void DreamyLove () {
fu(i, 2, n) {
auto[u, v, w] = edge[i];
g[v] = w;
}
fu(i, 2, n) pref[i] = pref[i - 1] + g[i];
pref[n + 1] = lnf;
auto chk = [&](ll mid, bool o) {
ll i = 1, cnt = 0;
vll c, vis(n+ 1, 0);
while(i <= n) {
ll j = i;
while(j <= n && pref[j] - pref[i] <= mid) j++;
ll place = j - 1;
c.pb(place); vis[place] = 1;
ll cover = pref[place] + mid;
ll t = place;
while (t + 1 <= n && pref[t + 1] <= cover) t++;
i = t + 1; cnt++;
}
if(o) {
fu(i, 1, n) if(!vis[i] && c.size() < k) c.pb(i);
for(auto&i: c) cout << i << ' ';
}
return (cnt <= k);
};
// chk(4, 1);
ll l = 0, r = pref[n], sad = 0;
while(l <= r) {
ll m = l + (r - l) / 2;
if(chk(m, 0)) r = m - 1, sad = m;
else l = m + 1;
}
cout << sad << '\n';
chk(sad, 1);
//
}
}
namespace LoveLast {
ll maxReach[mxn], minDist[mxn];
vll c, vis;
void dfs(ll u, ll p, ll r) {
for(auto&[v, w]: graph[u]) {
if(v == p) continue;
dfs(v, u, r);
if(maxReach[v] + min(w, minDist[v]) <= r) {
if(maxReach[v] + minDist[v] > r) maximize(maxReach[u], maxReach[v] + w);
minimize(minDist[u], minDist[v] + w);
} else {
c.pb(v); vis[v] = 1;
minimize(minDist[u], w);
}
}
}
bool check (ll r, ll o) {
c.clear(); vis.assign(n + 7, 0);
memset(minDist, 0x3f, sizeof(minDist));
memset(maxReach, 0, sizeof(maxReach));
dfs(1, 0, r);
if (maxReach[1] + minDist[1] > r) c.push_back(1), vis[i] = 1;
if(o) {
fu(i, 1, n) if(!vis[i] && c.size() < k) c.pb(i);
for(auto&i: c) cout << i << ' ';
}
return (c.size() <= k);
}
void DreamyLove () {
// cerr << check(8, 1);
ll l = 0, r = 1e15, sad = 0;
while(l <= r) {
ll m = l + (r - l) / 2;
if(check(m, 0)) sad = m, r = m - 1;
else l = m + 1;
}
cout << sad << '\n';
check(sad, 1);
//
}
}
void lovesper(const ll &TestCase) {
cin >> n >> k;
fu(i, 2, n) {
ll u, v, w; cin >> u >> v >> w;
graph[u].pb({v, w});
graph[v].pb({u, w});
edge[i] = {u, v, w};
}
if(Love1::check()) {
Love1::DreamyLove();
return;
}
if(Love2::check()) {
Love2::DreamyLove();
return;
}
if(Love3::check()) {
Love3::DreamyLove();
return;
}
LoveLast::DreamyLove();
}
signed main() {
LIFESUCK
#define name "lovesper"
// freopen(name".inp", "r", stdin);
// freopen(name".out", "w", stdout);
ll Test = 1;
// cin >> Test;
fu(i, 1, Test) {
lovesper(i);
if (i < Test) cout << '\n';
}
return 0;
}