Submission #825844

#	Time	Username	Problem	Language	Result	Execution time	Memory
825844		karrigan	Parkovi (COCI22_parkovi)	C++17	0 / 110	232 ms	28228 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define bit(n,i) ((n>>i)&1)
#define all(x) x.begin(),x.end()
//#pragma GCC optimize("O2,unroll-loops")
//#pragma GCC target("avx,avx2,bmi,bmi2,sse,sse2,sse3,ssse3,sse4,popcnt")
#define int long long
typedef long long ll;
typedef pair<int,int> pii;
typedef double ld;
typedef pair<ld,ld> pdd;
typedef pair<ll,ll> pll;
const ll maxn=2e5+2;
const ll offset=1e9;
const ll block=317;
const ll inf=1e18;
const ll mod=1e9+7;
int n,k,g,up[maxn],selllll;
bool ed[maxn];
vector<pii> adj[maxn];
vector<int> res;
void cc(int u,int pass)
{
//    cerr<<"asdasd "<< u<<'\n';
    res.pb(u);
    up[u]=pass;
    ed[u]=1;
    selllll++;
}
void dfs(int u,int pre,int last)
{
    //cerr<<u<<'\n';
    for(auto x: adj[u])
    {
        int v=x.fi,w=x.se;
        if (v==pre) continue;
        dfs(v,u,w);
    }
    if (last>g)
    {
        cc(u,last);
        return;
    }
    int mx1=0,mx2=0;
    for(auto x: adj[u])
    {
        int v=x.fi,w=x.se;
        if (v==pre) continue;
        if (last+up[v]>g && !ed[v])
        {
            cc(u,last);
            return;
        }
        if (!ed[v])
        {
            if (up[v]>= mx1)
            {
                mx2=mx1;
                mx1=up[v];
            }
            else if (up[v]>=mx2)
            {
                mx2=up[v];
            }
        }

    }
//    if (u==3)
//    {
//        cerr<< mx1<<' '<< mx2<<'\n';
//    }
    if (mx1+mx2>g)
    {
        cc(u,last);
        return;
    }
    up[u]=mx1+last;
}
bool check(int l)
{
    res.clear();
    g=l;
    selllll=0;
    for1(i,1,n)
    {
        up[i]=0;
        ed[i]=0;
    }
    dfs(1,0,0);
//    cerr<< selllll<<'\n';
    return (selllll<=k);

}
void sol()
{
    cin >> n>> k;
    for1(i,1,n-1)
    {
        int u,v,w;cin >> u>>v>>w;
        adj[u].pb({v,w});
        adj[v].pb({u,w});
    }
    int l=0,r=1e14,mid;
    while (l<=r)
    {
        //cerr<< l<<'\n';
        mid=l+r>>1;
        if (check(mid)) r=mid-1;
        else l=mid+1;
    }
    cout << l;
    cout << '\n';
    check(l);
    if (res.size()<k)
    {
        for1(i,1,n)
        {
            if (!ed[i]) res.pb(i);
            if (res.size()==k) break;
        }
    }
    for(int v: res) cout << v<<' ';
       // cerr<< check(8);

}
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t=1;//cin >> t;
    while(t--)
    {
        sol();
    }
}
/*

6 3
2 1 7
3 1 2
3 4 6
1 5 9
1 6 6
*/

Compilation message (stderr)

Main.cpp: In function 'void dfs(long long int, long long int, long long int)':
Main.cpp:53:20: warning: unused variable 'w' [-Wunused-variable]
   53 |         int v=x.fi,w=x.se;
      |                    ^
Main.cpp: In function 'void sol()':
Main.cpp:113:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  113 |         mid=l+r>>1;
      |             ~^~
Main.cpp:120:19: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
  120 |     if (res.size()<k)
      |         ~~~~~~~~~~^~
Main.cpp:125:27: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
  125 |             if (res.size()==k) break;
      |                 ~~~~~~~~~~^~~

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