Submission #696661

#TimeUsernameProblemLanguageResultExecution timeMemory
696661SanguineChameleonParkovi (COCI22_parkovi)C++17
20 / 110
3068 ms24332 KiB
// BEGIN BOILERPLATE CODE #include <bits/stdc++.h> using namespace std; #ifdef KAMIRULEZ const bool kami_loc = true; const long long kami_seed = 69420; #else const bool kami_loc = false; const long long kami_seed = chrono::steady_clock::now().time_since_epoch().count(); #endif const string kami_fi = "kamirulez.inp"; const string kami_fo = "kamirulez.out"; mt19937_64 kami_gen(kami_seed); long long rand_range(long long rmin, long long rmax) { uniform_int_distribution<long long> rdist(rmin, rmax); return rdist(kami_gen); } long double rand_real(long double rmin, long double rmax) { uniform_real_distribution<long double> rdist(rmin, rmax); return rdist(kami_gen); } void file_io(string fi, string fo) { if (fi != "" && (!kami_loc || fi == kami_fi)) { freopen(fi.c_str(), "r", stdin); } if (fo != "" && (!kami_loc || fo == kami_fo)) { freopen(fo.c_str(), "w", stdout); } } void set_up() { if (kami_loc) { file_io(kami_fi, kami_fo); } ios_base::sync_with_stdio(0); cin.tie(0); } void just_do_it(); void just_exec_it() { if (kami_loc) { auto pstart = chrono::steady_clock::now(); just_do_it(); auto pend = chrono::steady_clock::now(); long long ptime = chrono::duration_cast<chrono::milliseconds>(pend - pstart).count(); string bar(50, '='); cout << '\n' << bar << '\n'; cout << "Time: " << ptime << " ms" << '\n'; } else { just_do_it(); } } int main() { set_up(); just_exec_it(); return 0; } // END BOILERPLATE CODE // BEGIN MAIN CODE const long long inf = 1e18L + 20; const int ms = 2e5 + 20; vector<pair<int, int>> adj[ms]; bool f[ms]; long long de[ms]; long long mx[ms]; int best = -1; long long res = inf; int n, k; void dfs(int u, int pr) { for (auto x: adj[u]) { int v = x.first; int w = x.second; if (v != pr) { de[v] = de[u] + w; dfs(v, u); } } } void sub2() { de[1] = 0; dfs(1, -1); int d1 = 1; for (int i = 1; i <= n; i++) { if (de[i] > de[d1]) { d1 = i; } } de[d1] = 0; dfs(d1, -1); int d2 = 1; for (int i = 1; i <= n; i++) { mx[i] = max(mx[i], de[i]); if (de[i] > de[d2]) { d2 = i; } } de[d2] = 0; dfs(d2, -1); for (int i = 1; i <= n; i++) { mx[i] = max(mx[i], de[i]); } int best = 1; for (int i = 1; i <= n; i++) { if (mx[i] < mx[best]) { best = i; } } cout << mx[best] << '\n'; cout << best << '\n'; } void just_do_it() { cin >> n >> k; for (int i = 0; i < n - 1; i++) { int u, v, w; cin >> u >> v >> w; adj[u].push_back({v, w}); adj[v].push_back({u, w}); } if (k == 1) { sub2(); return; } for (int i = 0; i < (1 << n); i++) { if (__builtin_popcount(i) != k) { continue; } for (int j = 0; j < n; j++) { if ((i >> j) & 1) { f[j + 1] = true; } else { f[j + 1] = false; } } long long cur = 0; for (int j = 1; j <= n; j++) { de[j] = 0; dfs(j, -1); long long mi = inf; for (int k = 1; k <= n; k++) { if (f[k]) { mi = min(mi, de[k]); } } cur = max(cur, mi); } if (cur < res) { res = cur; best = i; } } cout << res << '\n'; for (int i = 0; i < n; i++) { if ((best >> i) & 1) { cout << (i + 1) << " "; } } } // END MAIN CODE

Compilation message (stderr)

Main.cpp: In function 'void file_io(std::string, std::string)':
Main.cpp:30:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |   freopen(fi.c_str(), "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:33:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |   freopen(fo.c_str(), "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...