제출 #1265776

#제출 시각아이디문제언어결과실행 시간메모리
1265776thecybRace (IOI11_race)C++17
100 / 100
727 ms39876 KiB
#include <bits/stdc++.h> void steroids(const std::string &s = "", const std::string &file_in = ".in", const std::string &file_out = ".out") { std::cin.tie(0) -> sync_with_stdio(0); if (!s.empty()) { freopen((s + file_in).c_str(), "r", stdin); freopen((s + file_out).c_str(), "w", stdout); } } const int N = 2e5; std::vector<std::pair<int, int>> adj[N]; int sub_sz[N]; bool del[N]; int n, k, ans; std::map<int, int> current; std::vector<std::pair<int, int>> to_be_merged; int dfs_sz(const int &u, const int &p) { sub_sz[u] = 1; for (const auto &[v, _] : adj[u]) { if (v == p || del[v]) continue; sub_sz[u] += dfs_sz(v, u); } return sub_sz[u]; } int get_centroid(const int &u, const int &p, const int &sz) { for (const auto &[v, _] : adj[u]) { if (v == p || del[v]) continue; if (sub_sz[v] * 2 > sz) return get_centroid(v, u, sz); } return u; } void get_dist_to_centroid(const int &u, const int &p, const int &d, const int &l) { if (d > k) return; to_be_merged.push_back({d, l}); for (const auto &[v, w] : adj[u]) { if (v == p || del[v]) continue; get_dist_to_centroid(v, u, d+w, l+1); } } void ctd(const int &u) { int centroid = get_centroid(u, -1, dfs_sz(u, -1)); del[centroid] = true; current.clear(); to_be_merged.clear(); for (const auto &[child, dist] : adj[centroid]) { if (del[child]) continue; get_dist_to_centroid(child, centroid, dist, 1); for (const auto &[d, l] : to_be_merged) { if (current.find(k - d) != current.end()) ans = std::min(ans, current[k-d] + l); else if (d == k) ans = std::min(ans, l); } for (const auto &[d, l] : to_be_merged) { if (current.count(d)) current[d] = std::min(current[d], l); else current[d] = l; } to_be_merged.clear(); } for (const auto &[nxt, _] : adj[centroid]) { if (!del[nxt]) ctd(nxt); } } int best_path(int nn, int kk, int h[][2], int l[]) { n = nn; k = kk; ans = n; for (int i = 0; i < n; i++) { int u = h[i][0], v = h[i][1], w = l[i]; adj[u].push_back({v, w}); adj[v].push_back({u, w}); } ctd(0); return (ans == n ? -1 : ans); }

컴파일 시 표준 에러 (stderr) 메시지

race.cpp: In function 'void steroids(const string&, const string&, const string&)':
race.cpp:6:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    6 |     freopen((s + file_in).c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
race.cpp:7:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    7 |     freopen((s + file_out).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...