Submission #1225515

#	Time	Username	Problem	Language	Result	Execution time	Memory
1225515		Dreamy_lovesper	Parkovi (COCI22_parkovi)	C++20	50 / 110	521 ms	37312 KiB

Main

#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);
        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;
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 30 / 30
• Subtask 4: 0 / 60