Submission #696689

#	Time	Username	Problem	Language	Result	Execution time	Memory
696689		socpite	Parkovi (COCI22_parkovi)	C++14	20 / 110	212 ms	68268 KiB

Main

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

#define f first
#define s second

typedef long long ll;
typedef long double ld;

const int mod = 1e9+7;
const int maxn = 2e5+5;
const ll inf = 1e18+5;

ll dist = inf;
int pos;
int n, k;

ll dp[maxn];
ll E[maxn];

vector<pair<int, int>> g[maxn];

void dfs(int x, int msk, int p = 0, ll d = 0){
    //cout << x << " " << msk << "\n";
    if(msk&(1<<(x-1)))dist = min(dist, d);
    for(auto v: g[x]){
        if(v.f == p)continue;
        dfs(v.f, msk, x, d+v.s);
    }
}

void dfs1(int x, int p){
    for(auto v: g[x]){
        if(v.f == p)continue;
        dfs1(v.f, x);
        dp[x] = max(dp[x], dp[v.f] + v.s);
    }
}

void solve(int x, int p, ll d){
    //cout << x << " " << d << "\n";
    if(max(d, dp[x]) < dist){
        dist = max(d, dp[x]);
        pos = x;
    }
    vector<pair<int, int>> cc;
    for(auto v: g[x])if(v.f != p)cc.push_back(v);
    if(cc.empty())return;
    vector<ll> pfx(cc.size()), sfx(cc.size());
    pfx[0] = dp[cc[0].f]+cc[0].s;
    sfx[cc.size()-1] = dp[cc[cc.size()-1].f]+cc[cc.size()-1].s;
    for(int i = 1; i < cc.size(); i++)pfx[i] = max(pfx[i-1], dp[cc[i].f] + cc[i].s);
    for(int i = cc.size()-2; i >= 0; i--)sfx[i] = max(sfx[i+1], dp[cc[i].f]+cc[i].s);
    for(int i = 0; i < cc.size(); i++){
        ll tmp = d;
        if(i)tmp = max(tmp, pfx[i-1]);
        if(i+1 < cc.size())tmp = max(tmp, sfx[i+1]);
        solve(cc[i].f, x, tmp+cc[i].s);
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> k;
    for(int i = 0; i < n-1; i++){
        int a, b, w;
        cin >> a >> b >> w;
        E[i] = w;
        g[a].push_back({b, w});
        g[b].push_back({a, w});
    }
    ll ans = inf;
    if(n <= 20){
        for(int i = 0; i < (1<<n) ; i++){
            if(__builtin_popcount(i) != k)continue;
            ll mx = 0;
            for(int j = 1; j <= n; j++){
                dist = inf;
                dfs(j, i);
                mx = max(mx, dist);
            }
            if(ans > mx){
                ans = mx;
                pos = i;
            }
        }
        cout << ans << "\n";
        for(int i = 0; i < n; i++)if(pos&(1<<i))cout << i+1 << " ";
    }
    else if(k == 1){
        dfs1(1, 0);
        solve(1, 0, 0);
        cout << dist << "\n" << pos;
    }
    
}

Compilation message (stderr)

Main.cpp: In function 'void solve(int, int, ll)':
Main.cpp:52:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |     for(int i = 1; i < cc.size(); i++)pfx[i] = max(pfx[i-1], dp[cc[i].f] + cc[i].s);
      |                    ~~^~~~~~~~~~~
Main.cpp:54:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |     for(int i = 0; i < cc.size(); i++){
      |                    ~~^~~~~~~~~~~
Main.cpp:57:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |         if(i+1 < cc.size())tmp = max(tmp, sfx[i+1]);
      |            ~~~~^~~~~~~~~~~

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