Submission #696934

#TimeUsernameProblemLanguageResultExecution timeMemory
696934Do_you_copyParkovi (COCI22_parkovi)C++17
0 / 110
666 ms45372 KiB
//Then #include <bits/stdc++.h> #define pb push_back #define fi first #define se second #define faster ios_base::sync_with_stdio(0); cin.tie(0); #define int long long using namespace std; using ll = long long; using ld = long double; using pii = pair <int, int>; mt19937_64 Rand(chrono::steady_clock::now().time_since_epoch().count()); const int maxN = 3e5 + 1; //const int Mod = 1e9 + 7; //const int inf = int n, k; vector <pii> adj[maxN]; ll mid, cnt; ll dp[maxN]; set <int> S; bool visited[maxN]; void dfs(int u, int p){ dp[u] = 0; int maxx = 0; visited[u] = 1; for (auto i: adj[u]){ if (i.fi == p || i.se > mid) continue; dfs(i.fi, u); if (dp[i.fi] + i.se > mid){ ++cnt; S.insert(i.fi); if (dp[u] < i.se){ maxx = dp[u]; dp[u] = i.se; } else maxx = max(maxx, i.se); } else{ if (dp[u] < dp[i.fi] + i.se){ maxx = dp[u]; dp[u] = dp[i.fi] + i.se; } else maxx = max(maxx, dp[i.fi] + i.se); } } if (u == p && maxx + dp[u] > mid){ S.insert(u); ++cnt; } } bool check(){ S.clear(); fill(visited + 1, visited + n + 1, 0); int res = 0; for (int i = 1; i <= n; ++i){ cnt = 0; if (!visited[i]){ dfs(i, i); if (!cnt){ S.insert(i); ++res; } else res += cnt; } } return res <= k; } void Init(){ cin >> n >> k; for (int i = 1; i < n; ++i){ int u, v, w; cin >> u >> v >> w; adj[u].pb({v, w}); adj[v].pb({u, w}); } ll l = 1, r = 1e4; while (l < r){ mid = (l + r) >> 1; if (check()) r = mid; else l = mid + 1; } mid = l; check(); cout << l << "\n"; for (int i = 1; i <= n; ++i){ if (S.size() == k) break; S.insert(i); } for (auto i: S) cout << i << " "; } #define debug #define taskname "test" signed main(){ faster if (fopen(taskname".inp", "r")){ freopen(taskname".inp", "r", stdin); freopen(taskname".out", "w", stdout); } int tt = 1; //cin >> tt; while (tt--){ Init(); } if (fopen("timeout.txt", "r")){ ofstream timeout("timeout.txt"); timeout << signed(double(clock()) / CLOCKS_PER_SEC * 1000); timeout.close(); #ifndef debug cerr << "Time elapsed: " << signed(double(clock()) / CLOCKS_PER_SEC * 1000) << "ms\n"; #endif // debug } }

Compilation message (stderr)

Main.cpp: In function 'void Init()':
Main.cpp:88:22: warning: comparison of integer expressions of different signedness: 'std::set<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   88 |         if (S.size() == k) break;
      |             ~~~~~~~~~^~~~
Main.cpp: In function 'int main()':
Main.cpp:99:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   99 |         freopen(taskname".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:100:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  100 |         freopen(taskname".out", "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...