Submission #533525

#	Time	Username	Problem	Language	Result	Execution time	Memory
533525		N1NT3NDO	Parkovi (COCI22_parkovi)	C++14	10 / 110	85 ms	31332 KiB

Main

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#define sz(x) (int)x.size()
#define fi first
#define sd second
#define all(x) x.begin(), x.end()
//#pragma GCC target ("avx2")
//#pragma GCC optimization ("O3")
//#pragma GCC optimization ("unroll-loops")

using namespace std;
//using namespace __gnu_pbds;

//typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

#define int long long

const int N = (int)2e5 + 500;
vector< pair<int, int> > g[N];
int n, k, mx, mn_d, dp[N], dp1[N];
bool have[N];

void dfs(int v, int pr, int d, int cur)
{
    if (have[v])
    {
        mx = min(mx, cur);

        return;
    }

    for(auto [u, w] : g[v])
    {
        if (u == pr) continue;
        dfs(u, v, d + 1, cur + w);
    }
}

void dfs1(int v, int pr, int cst)
{
    dp1[v] = max(dp1[pr], dp[pr]) + cst;
    for(auto [u, w] : g[v])
    {
        if (u == pr) continue;
        dfs1(u, v, w);
        dp[v] = max(dp[v], dp[u] + w);
    }
}

void group1()
{
    vector<int> vec;
    int ans = 1e18;
    for(int mask = 0; mask < (1 << n); mask++)
    {
        if (__builtin_popcount(mask) != k) continue;

        for(int i = 1; i <= n; i++) have[i] = 0;
        for(int i = 0; i < n; i++)
          if (mask & (1 << i))
            {
                have[i + 1] = 1;
            }


        int cur_ans = 0;
        for(int i = 1; i <= n; i++)
        {
            mx = 1e18; mn_d = 1e18;
            dfs(i, i, 0, 0);
            cur_ans = max(cur_ans, mx);
        }

        if (ans > cur_ans)
        {
            ans = cur_ans;
            vec.clear();
            for(int i = 0; i < n; i++)
              if (mask & (1 << i))
                vec.pb(i + 1);
        }
    }

    cout << ans << '\n';
    for(auto u : vec) cout << u << ' ';
}

void group2()
{
    dfs1(1, 1, 0);

    ll ans = 1e18;
    int nom;
    for(int i = 1; i <= n; i++)
    {
        ll mx = 0;
        for(auto [u, w] : g[i])
          mx = max({mx, dp[u], dp1[i]});
        if (mx < ans)
        {
            ans = mx;
            nom = i;
        }
    }

    cout << ans << '\n';
    cout << nom;
}

int32_t main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    //freopen("input.txt", "r", stdin);
    cin >> n >> k;
    for(int i = 1; i < n; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        g[u].pb({v, w});
        g[v].pb({u, w});
    }

    if (n <= 25) group1();
    else if (k == 1) group2();

}

Compilation message (stderr)

Main.cpp: In function 'void dfs(long long int, long long int, long long int, long long int)':
Main.cpp:35:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   35 |     for(auto [u, w] : g[v])
      |              ^
Main.cpp: In function 'void dfs1(long long int, long long int, long long int)':
Main.cpp:45:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   45 |     for(auto [u, w] : g[v])
      |              ^
Main.cpp: In function 'void group2()':
Main.cpp:100:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  100 |         for(auto [u, w] : g[i])
      |                  ^

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