Submission #696695

#	Time	Username	Problem	Language	Result	Execution time	Memory
696695		Hiennoob123	Parkovi (COCI22_parkovi)	C++14	0 / 110	240 ms	20372 KiB

Main

#include <bits/stdc++.h>
#define ll long long
#define pll pair<ll,ll>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
ll n, k;
ll A[200005];
vector<pll> T[200005];
ll val[200005];
ll Right[200005];
ll Left[200005];
ll dp[200005];
bool done[200005];
ll reroot[200005];
pll ans = mp(INT_MAX , 0);
bool check(ll value)
{
    ll cnt = 0;
    ll cur = 0;
    ll ptr = 1;
    for(int i = 1; i<= n; i++)
    {
        for(; ptr < n; ptr++)
        {
            if(cur+A[ptr]>value) break;
            cur += A[ptr];
        }
        Right[i] = ptr;
        cur-=A[i];
    }
    ptr = n-1;
    cur = 0;
    for(int i = n; i>= 1; i--)
    {
        for(; ptr > 0; ptr--)
        {
            if(cur+A[ptr]>value) break;
            cur += A[ptr];
        }
        Left[i] = ptr+1;
        cur-=A[i-1];
    }
    ll node = 1, Max = INT_MAX;
    for(int i = 1; i<= n; i++)
    {
        if(Left[i]>node) Max = min(Max, Right[i]);
        if(Max==i)
        {
            cnt++;
            node = i;
            Max = INT_MAX;
            continue;
        }
    }
    if(cnt<=k) return 1;
    return 0;
}
void print_ans(ll value)
{
    ll cnt = 0;
    ll cur = 0;
    ll ptr = 1;
    for(int i = 1; i<= n; i++)
    {
        for(; ptr < n; ptr++)
        {
            if(cur+A[ptr]>value) break;
            cur += A[ptr];
        }
        Right[i] = ptr;
        cur-=A[i];
    }
    ptr = n-1;
    cur = 0;
    for(int i = n; i>= 1; i--)
    {
        for(; ptr > 0; ptr--)
        {
            if(cur+A[ptr]>value) break;
            cur += A[ptr];
        }
        Left[i] = ptr+1;
        cur-=A[i-1];
    }
    vector<ll> save;
    ll node = 1, Max = INT_MAX;
    for(int i = 1; i<= n; i++)
    {
        if(Left[i]>node) Max = min(Max, Right[i]);
        //cout << Max << " " << i << "\n";
        if(Max==i)
        {
            cnt++;
            node = i;
            Max = INT_MAX;
            save.push_back(i);
            continue;
        }
    }
    cout << value << "\n";
    for(auto u: save) done[u] = 1;
    ll Le = k;
    Le -= save.size();
    for(int i = 1; i<= n; i++)
    {
        if(Le==0||done[i]) continue;
        done[i] = 1;
        Le--;
    }
    for(int i = 1; i<= n; i++) if(done[i]) cout << i << " ";
}
void solve_large()
{
    ll Max = 0;
    for(int i = 1; i< n; i++) Max = max(Max, val[i]);
    ll lo = 0, hi = 1e16, mid;
    while(hi-lo>1)
    {
        mid = ((hi+lo)>>1);
        //cout << lo << " " << hi << "\n";
        if(check(mid)) hi = mid;
        else lo = mid;
    }
    ll idx = 0;
    if(check(lo)) idx = lo;
    else idx = hi;
    print_ans(idx);
}
void dfs(ll v, ll par)
{
    for(auto u: T[v])
    {
        if(u.fi==par) continue;
        dfs(u.fi , v);
        dp[v] = max(dp[v], dp[u.fi]+u.se);
    }
    //cout << dp[v] << " " << v << "\n";
}
void dfsk(ll v, ll par)
{
    vector<pll> save;
    ll Max = reroot[v];
    for(auto u: T[v])
    {
        if(u.fi==par) continue;
        Max = max(Max, dp[u.fi]+u.se);
        save.push_back(mp(dp[u.fi]+u.se, u.fi));
    }
    ans = min(ans, mp(Max, v));
    save.push_back(mp(reroot[v], 0));
    save.push_back(mp(0 , 0));
    sort(save.begin(), save.end(), greater<pll>());
    for(auto u: T[v])
    {
        if(u.fi==par) continue;
        if(u.fi==save[0].se)
        {
            reroot[u.fi] = save[1].fi+u.se;
        }
        else
        {
            reroot[u.fi] = save[0].fi+u.se;
        }
    }
    //cout << v << " " << reroot[v] << "-\n";
    for(auto u: T[v])
    {
        if(u.fi==par) continue;
        dfsk(u.fi, v);
    }
}
void solve()
{
    cin >> n >> k;
    bool dt = 0;
    for(int i = 1; i< n; i++)
    {
        ll a, b, c; cin >> a >> b >> c;
        A[i] = val[i] = c;
        if(b!=a+1) dt = 1;
        T[a].push_back(mp(b,c));
        T[b].push_back(mp(a,c));
    }
    //cout << check(3) << "\n";
    if(!dt)
    {
        solve_large();
        return;
    }
    dfs(1 , 0);
    dfsk(1, 0);
    cout << ans.fi << "\n" << ans.se;
}
int main()
{
    ios_base::sync_with_stdio(NULL) ; cin.tie(nullptr) ; cout.tie(nullptr);
    //freopen("B.inp","r",stdin);
    ll test_case = 1;
    while(test_case--)
    {
        solve();
    }
}

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