Submission #533573

#	Time	Username	Problem	Language	Result	Execution time	Memory
533573		ggg	Parkovi (COCI22_parkovi)	C++14	0 / 110	44 ms	14708 KiB

Main

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define f first
#define s second
#define endl "\n"
using namespace std;

ll n,m,k,l,i,j,q,x,y,z,ans,an,a[209][209],pr[200009];
vector<vector<pair<ll,ll> > > v(100009);
vector<ll> w;

void DF(ll i,ll kol,ll pred)
{
  a[q][i]=kol; a[i][q]=kol;
  for (auto u : v[i])
    if (u.f!=pred)
      {
        DF(u.f,kol+u.s,i);
      }
}

int main()
{
  ios_base::sync_with_stdio(false); cin.tie(0);

  cin >>n>>m;
  for (i=1;i<n;i++)
    {
      cin >>x>>y>>z;
      v[x].pb({y,z});
      v[y].pb({x,z});
    }
  for (i=1;i<=n;i++)
    {
      q=i;
      DF(i,0,-1);
    }
  l=(1<<n)-1;
  ans=1e18; an=0;
  for (i=1;i<=l;i++)
    {
      if (__builtin_popcount(i)!=m) continue;
      w.clear();
      for (j=0;j<n;j++)
        if (i & (1<<j)) w.pb(j+1);
      x=0;
      for (j=1;j<=n;j++)
        {
          k=1e9;
          for (auto u : w)
            if (a[j][u]<k) k=min(k,a[j][u]);
          x=max(x,k);
        }
      if (x<=ans) { ans=x; an=i; }
    }
  cout <<ans<<endl;
  for (i=0;i<n;i++)
    if (an & (1<<i)) cout <<i+1<<" ";
}

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