제출 #851015

#제출 시각아이디문제언어결과실행 시간메모리
851015anhphantRailway (BOI17_railway)C++14
36 / 100
88 ms29384 KiB
#include <bits/stdc++.h> using namespace std; constexpr size_t N = 100000; size_t n, m, k, ans[N], l; vector<pair<int, int>> g[N]; vector<int> anc[N]; int x[N], h[N], r[N], preorder[N]; int trav(int u, int p, vector<int> &path, int j = 0) { preorder[u] = j++; h[u] = path.size(); for (size_t i = 1; i <= path.size(); i <<= 1) anc[u].push_back(path[path.size() - i]); path.push_back(u); for (auto const &[v, _] : g[u]) if (v != p) j = trav(v, u, path, j); path.pop_back(); return j; } int lift(int u, int y) { int z = 0; while (y) { if (y & 1) u = anc[u][z]; y >>= 1; ++z; } return u; } int lca(int u, int v) { if (h[u] < h[v]) u ^= v, v ^= u, u ^= v; u = lift(u, h[u] - h[v]); if (u == v) return u; for (size_t i = anc[u].size() - 1; i < anc[u].size(); --i) if (anc[u][i] != anc[v][i]) u = anc[u][i], v = anc[v][i]; return anc[u][0]; } void sum(int u, int p) { for (auto const &[v, i] : g[u]) if (v != p) sum(v, u), x[u] += x[v], ans[i] = x[v], l += x[v] >= 2 * k; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> n >> m >> k; for (size_t i = 0; i < n - 1; ++i) { int u, v; cin >> u >> v; g[u - 1].emplace_back(v - 1, i); g[v - 1].emplace_back(u - 1, i); } vector<int> path; trav(0, -1, path); for (size_t i = 0; i < m; ++i) { int s; cin >> s; for (size_t j = 0; j < s; ++j) cin >> r[j], --r[j]; sort(r, r + s, [](int const &u, int const &v) { return preorder[u] < preorder[v]; }); r[s] = r[0]; for (size_t j = 0; j < s; ++j) ++x[r[j]], ++x[r[j + 1]], x[lca(r[j], r[j + 1])] -= 2; } sum(0, -1); cout << l << '\n'; for (size_t i = 0; i < n - 1; ++i) if (ans[i] >= 2 * k) cout << i + 1 << ' '; cout << '\n'; }

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

railway.cpp: In function 'int trav(int, int, std::vector<int>&, int)':
railway.cpp:18:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   18 |     for (auto const &[v, _] : g[u])
      |                      ^
railway.cpp: In function 'void sum(int, int)':
railway.cpp:53:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   53 |     for (auto const &[v, i] : g[u])
      |                      ^
railway.cpp:55:63: warning: comparison of integer expressions of different signedness: 'int' and 'size_t' {aka 'long unsigned int'} [-Wsign-compare]
   55 |             sum(v, u), x[u] += x[v], ans[i] = x[v], l += x[v] >= 2 * k;
      |                                                          ~~~~~^~~~~~~~
railway.cpp: In function 'int main()':
railway.cpp:78:30: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   78 |         for (size_t j = 0; j < s; ++j)
      |                            ~~^~~
railway.cpp:83:30: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   83 |         for (size_t j = 0; j < s; ++j)
      |                            ~~^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...