제출 #330142

#제출 시각아이디문제언어결과실행 시간메모리
330142FalconRailway (BOI17_railway)C++17
36 / 100
100 ms33228 KiB
#pragma GCC optimize("O2") #include <bits/stdc++.h> #ifdef DEBUG #include "debug.hpp" #endif using namespace std; #define all(c) (c).begin(), (c).end() #define rall(c) (c).rbegin(), (c).rend() #define traverse(c, it) for(auto it = (c).begin(); it != (c).end(); ++it) #define rep(i, N) for(int i = 0; i < (N); ++i) #define rrep(i, N) for(int i = (N) - 1; i >= 0; --i) #define rep1(i, N) for(int i = 1; i <= (N); ++i) #define rep2(i, s, e) for(int i = (s); i <= (e); ++i) #define rep3(i, s, e, d) for(int i = (s); (d) >= 0 ? i <= (e) : i >= (e); i += (d)) #ifdef DEBUG #define debug(x...) { \ ++dbg::depth; \ string dbg_vals = dbg::to_string(x); \ --dbg::depth; \ dbg::fprint(__func__, __LINE__, #x, dbg_vals); \ } #define light_debug(x) { \ dbg::light = true; \ dbg::dout << __func__ << ":" << __LINE__; \ dbg::dout << " " << #x << " = " << x << endl; \ dbg::light = false; \ } #else #define debug(x...) 42 #define light_debug(x) 42 #endif using ll = long long; template<typename T> inline T& ckmin(T& a, T b) { return a = a > b ? b : a; } template<typename T> inline T& ckmax(T& a, T b) { return a = a < b ? b : a; } template<class Fun> class y_combinator_result { Fun fun_; public: template<class T> explicit y_combinator_result(T &&fun): fun_(std::forward<T>(fun)) {} template<class ...Args> decltype(auto) operator()(Args &&...args) { return fun_(std::ref(*this), std::forward<Args>(args)...); } }; template<class Fun> decltype(auto) y_combinator(Fun &&fun) { return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun)); } int main() { ios_base::sync_with_stdio(false); cin.tie(0); #ifdef DEBUG freopen("debug", "w", stderr); #endif int n, m, k; cin >> n >> m >> k; vector<vector<int>> adj(n); vector<int> edges(n - 1); rep(i, n - 1) { int u, v; cin >> u >> v; --u, --v; edges[i] = u ^ v; adj[u].push_back(i), adj[v].push_back(i); } vector<int> in(n), inv; vector<vector<int>> rmq; int t{}, h{}; { vector<int> tour; tour.reserve(2 * n); y_combinator([&](auto dfs, int u, int p) -> void { in[u] = t++; tour.push_back(in[u]); for(int e : adj[u]) { if(int v = edges[e] ^ u; v != p) dfs(v, u), tour.push_back(in[u]), ++t; } })(0, -1); debug(tour, t); inv.resize(t); fill(all(inv), -1); rep(i, n) inv[in[i]] = i; debug(in, inv); h = __lg(t) + 1; rmq = vector<vector<int>>(h, vector<int>(t)); rep(i, t) rmq[0][i] = tour[i]; rep(j, h - 1) rep(i, t) { rmq[j + 1][i] = rmq[j][i]; if(i + (1 << j) < t) ckmin(rmq[j + 1][i], rmq[j][i + (1 << j)]); } debug(rmq); } auto lca = [&](int u, int v) { u = in[u], v = in[v]; if(u > v) swap(u, v); int p = __lg(v - u + 1); return inv[min(rmq[p][u], rmq[p][v + 1 - (1 << p)])]; }; vector<int> up(n); rep(_, m) { int s; cin >> s; vector<int> v(s); rep(i, s) cin >> v[i], --v[i]; v.push_back(v[0]); rep(i, s) ++up[v[i]]; rep(i, s) --up[lca(v[i], v[i + 1])]; } debug(up); vector<int> k_edges; y_combinator([&](auto dfs, int u, int p) -> int { int s{up[u]}; for(int e : adj[u]) if(e != p) s += dfs(edges[e] ^ u, e); if(s >= k) k_edges.push_back(p); return s; })(0, -1); cout << k_edges.size() << '\n'; sort(all(k_edges)); for(int& e : k_edges) cout << e + 1 << ' '; cout << '\n'; #ifdef DEBUG dbg::dout << "\nExecution time: " << clock() * 1000 / CLOCKS_PER_SEC << "ms" << endl; #endif return 0; }

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

railway.cpp: In function 'int main()':
railway.cpp:35:29: warning: statement has no effect [-Wunused-value]
   35 | #define debug(x...)         42
      |                             ^~
railway.cpp:96:9: note: in expansion of macro 'debug'
   96 |         debug(tour, t);
      |         ^~~~~
railway.cpp:35:29: warning: statement has no effect [-Wunused-value]
   35 | #define debug(x...)         42
      |                             ^~
railway.cpp:99:9: note: in expansion of macro 'debug'
   99 |         debug(in, inv);
      |         ^~~~~
railway.cpp:35:29: warning: statement has no effect [-Wunused-value]
   35 | #define debug(x...)         42
      |                             ^~
railway.cpp:110:9: note: in expansion of macro 'debug'
  110 |         debug(rmq);
      |         ^~~~~
railway.cpp:35:29: warning: statement has no effect [-Wunused-value]
   35 | #define debug(x...)         42
      |                             ^~
railway.cpp:127:5: note: in expansion of macro 'debug'
  127 |     debug(up);
      |     ^~~~~
#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...