oj.uz

Submission #696688

# Submission time Handle Problem Language Result Execution time Memory
696688 2023-02-07T04:01:51 Z socpite Parkovi (COCI22_parkovi) C++14
10 / 110
 169 ms 76108 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 = 5e5+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 <= 0){
        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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 12032 KB Unexpected end of file - int64 expected
2 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 73676 KB Output is correct
2 Correct 127 ms 76108 KB Output is correct
3 Correct 100 ms 27000 KB Output is correct
4 Correct 168 ms 22708 KB Output is correct
5 Correct 158 ms 22432 KB Output is correct
6 Correct 148 ms 22348 KB Output is correct
7 Correct 138 ms 22476 KB Output is correct
8 Correct 169 ms 23124 KB Output is correct
9 Correct 146 ms 22796 KB Output is correct
10 Correct 152 ms 23036 KB Output is correct
11 Correct 119 ms 27500 KB Output is correct
12 Correct 123 ms 28836 KB Output is correct
13 Correct 132 ms 30424 KB Output is correct
14 Correct 108 ms 28492 KB Output is correct
15 Correct 109 ms 27044 KB Output is correct
16 Correct 115 ms 28760 KB Output is correct
17 Correct 129 ms 26920 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 70 ms 19660 KB Unexpected end of file - int64 expected
2 Halted 0 ms 0 KB -

Subtask #4
0 / 60.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 12032 KB Unexpected end of file - int64 expected
2 Halted 0 ms 0 KB -