Submission #849026

#	Time	Username	Problem	Language	Result	Execution time	Memory
849026		tiwerlol	Parkovi (COCI22_parkovi)	C++17	110 / 110	1300 ms	56884 KiB

Main

#include <bits/stdc++.h>
using namespace std;

ofstream fout("xor.out");
ifstream fin("xor.in");

#define miauDebug
#ifdef miauDebug
#define mau(x) MIAUMIAU(#x, x)
#else
#define mau(x)
#endif

void MIAUMIAU(const char* var_name, auto var_value) {
    cout << var_name << " = " << var_value << endl;
}

using ll = long long;
const int nM = 2e5+5;
const ll MOD = 1e9 + 7;
// :3

vector<vector<pair<int, ll>>> node;
vector<ll> dist(nM), reach(nM), ans;
int f;
void dfs(int a, int p, ll mid, ll c, bool sw)
{
    reach[a]=- 6e17;
    dist[a] =  6e17;

    for(auto x : node[a])
    {
        if(x.first!=p)
        {
            dfs(x.first, a, mid, x.second, sw);
            reach[a] = max(reach[x.first] + x.second, reach[a]);
            dist[a] = min(dist[x.first] + x.second, dist[a]);
        }
    }

    if(dist[a] > mid && reach[a] < 0)
        reach[a] = 0;

    if(dist[a] + reach[a] <= mid)
    {
        reach[a]=- 6e17;
        return;
    }

    if(reach[a] + c > mid || (a==1 && (reach[a] >= 0)))
    {
        if(sw)
        {
            ans.push_back(a);
        }
        f++;
        reach[a] = - 6e17;
        dist[a] = 0;
    }
}

void solve() {
    int n, k; cin >> n >> k;

    node = vector<vector<pair<int, ll>>> (n+2);

    for(int z = 1; z < n; z++)
    {
        int a, b, w; cin >> a >> b >> w;

        node[a].push_back(make_pair(b, w));
        node[b].push_back(make_pair(a, w));
    }

    ll l = 0, r = 1e16;
    ll mn = 1e16;

    while(l<=r)
    {
        ll mid = (l+r)/2;
        dfs(1, 0, mid, 0, 0);

        if(f <= k)
        {
            mn = mid;
            r = mid-1;
        } else
        {
            l = mid+1;
        }
        f = 0;
    }

    cout << mn << '\n';

    dfs(1, 0, mn, 0, 1);
    map<int, int> miau;
    for(auto x : ans)
        miau[x]=1;
    if(ans.size()==k)
    {
        for(auto x : ans)
            cout << x << ' ';
        return;
    }

    for(int z = 1; z <= n; z++)
    {
        if(!miau[z]) ans.push_back(z);
        if(ans.size()==k)
        {
            for(auto x : ans)
                cout << x << ' ';
            return;
        }
    }
}
signed main()
{
    cout.tie(NULL);
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);

    int tt = 1; //cin >> tt;

    while(tt--)
        solve();
}

Compilation message (stderr)

Main.cpp:14:37: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   14 | void MIAUMIAU(const char* var_name, auto var_value) {
      |                                     ^~~~
Main.cpp: In function 'void solve()':
Main.cpp:100:18: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  100 |     if(ans.size()==k)
      |        ~~~~~~~~~~^~~
Main.cpp:110:22: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  110 |         if(ans.size()==k)
      |            ~~~~~~~~~~^~~

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