oj.uz

Submission #696687

# Submission time Handle Problem Language Result Execution time Memory
696687 2023-02-07T04:01:16 Z socpite Parkovi (COCI22_parkovi) C++14
10 / 110
 214 ms 468 KB 
#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 = 65;
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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 212 KB Output is correct
2 Correct 5 ms 212 KB Output is correct
3 Correct 7 ms 320 KB Output is correct
4 Correct 3 ms 212 KB Output is correct
5 Correct 6 ms 212 KB Output is correct
6 Correct 42 ms 212 KB Output is correct
7 Correct 45 ms 212 KB Output is correct
8 Correct 16 ms 212 KB Output is correct
9 Correct 211 ms 304 KB Output is correct
10 Correct 16 ms 324 KB Output is correct
11 Correct 106 ms 300 KB Output is correct
12 Correct 214 ms 212 KB Output is correct
13 Correct 7 ms 324 KB Output is correct
14 Correct 104 ms 300 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 468 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 1 ms 468 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 5 ms 212 KB Output is correct
2 Correct 5 ms 212 KB Output is correct
3 Correct 7 ms 320 KB Output is correct
4 Correct 3 ms 212 KB Output is correct
5 Correct 6 ms 212 KB Output is correct
6 Correct 42 ms 212 KB Output is correct
7 Correct 45 ms 212 KB Output is correct
8 Correct 16 ms 212 KB Output is correct
9 Correct 211 ms 304 KB Output is correct
10 Correct 16 ms 324 KB Output is correct
11 Correct 106 ms 300 KB Output is correct
12 Correct 214 ms 212 KB Output is correct
13 Correct 7 ms 324 KB Output is correct
14 Correct 104 ms 300 KB Output is correct
15 Runtime error 1 ms 468 KB Execution killed with signal 11
16 Halted 0 ms 0 KB -