oj.uz

Submission #533573

# Submission time Handle Problem Language Result Execution time Memory
533573 2022-03-06T10:24:14 Z ggg Parkovi (COCI22_parkovi) C++14
0 / 110
 44 ms 14708 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2636 KB Output is correct
2 Correct 4 ms 2636 KB Output is correct
3 Correct 4 ms 2636 KB Output is correct
4 Correct 4 ms 2636 KB Output is correct
5 Correct 4 ms 2636 KB Output is correct
6 Correct 9 ms 2636 KB Output is correct
7 Incorrect 9 ms 2636 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 41 ms 14708 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 44 ms 14660 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2636 KB Output is correct
2 Correct 4 ms 2636 KB Output is correct
3 Correct 4 ms 2636 KB Output is correct
4 Correct 4 ms 2636 KB Output is correct
5 Correct 4 ms 2636 KB Output is correct
6 Correct 9 ms 2636 KB Output is correct
7 Incorrect 9 ms 2636 KB Output isn't correct
8 Halted 0 ms 0 KB -