제출 #877194

#제출 시각아이디문제언어결과실행 시간메모리
877194kh0iPastiri (COI20_pastiri)C++17
100 / 100
485 ms82168 KiB
#include "bits/stdc++.h" using namespace std; #ifdef LOCAL #include "debug.h" #else #define debug(...) #endif using ll = long long; using pii = pair<int, int>; #define F first #define S second #define sz(x) (int)((x).size()) #define all(x) (x).begin(), (x).end() mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); ll get_rand(ll l, ll r) { assert(l <= r); return uniform_int_distribution<ll> (l, r)(rng); } const int N = 5e5 + 3; int n, k, x[N]; vector<int> g[N]; int dist[N], h[N], opt[N]; void bfs(){ memset(dist, 0x3f, sizeof(dist)); queue<int> qu; for(int i = 1; i <= k; ++i){ dist[x[i]] = 0; qu.push(x[i]); } while(!qu.empty()){ int u = qu.front(); qu.pop(); for(int v : g[u]){ if(dist[v] > dist[u] + 1){ dist[v] = dist[u] + 1; qu.push(v); } } } } void dfs_pre(int u, int pre, int mx, int st){ int p = h[u] + dist[u]; if(p > mx){ mx = p; st = u; } opt[u] = st; for(int v : g[u]){ if(v == pre) continue; h[v] = h[u] + 1; dfs_pre(v, u, mx, st); } } bool good[N]; void dfs_fill(int u){ good[u] = 1; for(int v : g[u]) if(!good[v] and dist[v] + 1 == dist[u]) dfs_fill(v); } void solve(){ cin >> n >> k; for(int i = 1; i < n; ++i){ int u, v; cin >> u >> v; g[u].push_back(v); g[v].push_back(u); } for(int i = 1; i <= k; ++i) cin >> x[i]; bfs(); dfs_pre(1, 0, -1, 1); sort(x + 1, x + k + 1, [](int &dak, int &mim) -> bool{ return h[dak] > h[mim]; }); vector<int> res; for(int i = 1; i <= k; ++i){ if(!good[x[i]]){ res.push_back(opt[x[i]]); dfs_fill(opt[x[i]]); } } cout << sz(res) << '\n'; for(int i : res) cout << i << ' '; } int32_t main() { cin.tie(nullptr)->sync_with_stdio(0); #define task "sheep" if(fopen(task".inp", "r")){ freopen(task".inp", "r", stdin); freopen(task".out", "w", stdout); } int test = 1; // cin >> test; for(int i = 1; i <= test; ++i){ // cout << "Case #" << i << ": "; solve(); } #ifdef LOCAL cerr << "\n[Time]: " << 1000.0 * clock() / CLOCKS_PER_SEC << " ms.\n"; #endif return 0; }

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

pastiri.cpp: In function 'int32_t main()':
pastiri.cpp:105:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  105 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
pastiri.cpp:106:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  106 |         freopen(task".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...