Submission #696688

#TimeUsernameProblemLanguageResultExecution timeMemory
696688socpiteParkovi (COCI22_parkovi)C++14
10 / 110
169 ms76108 KiB
#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 (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]);
      |            ~~~~^~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...