Submission #714578

#TimeUsernameProblemLanguageResultExecution timeMemory
714578IliyaRailway (BOI17_railway)C++17
7 / 100
125 ms27240 KiB
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N = 1e5 + 10, Log = 20; vector<int> Adj[N]; vector<pair<int, int>> E; int n, m, k, H[N], P[Log][N], ts, S[N], F[N], O[N]; void PreDFS(int v, int p) { S[v] = ++ts; P[0][v] = p; for (int i = 1; i < Log; i++) P[i][v] = P[i - 1][P[i - 1][v]]; for (int u : Adj[v]) if (u != p) H[u] = H[v] + 1, PreDFS(u, v); F[v] = ts; } int LCA(int u, int v) { if (H[u] < H[v]) swap(u, v); for (int i = 0; i < Log; i++) if ((H[u] - H[v]) & (1 << i)) u = P[i][u]; if (u == v) return u; for (int i = Log - 1; ~i; i--) if (P[i][u] != P[i][v]) u = P[i][u], v = P[i][v]; return P[0][v]; } void DFS(int v, int p) { for (int u : Adj[v]) if (u != p) DFS(u, v), O[v] += O[u]; } signed main() { scanf("%d%d%d", &n, &m, &k); for (int i = 1; i < n; i++) { int u, v; scanf("%d%d", &u, &v); E.push_back({u, v}); Adj[u].push_back(v); Adj[v].push_back(u); } PreDFS(1, 1); while (m--) { int s; scanf("%d", &s); vector<int> V; for (int i = 0; i < s; i++) { int v; scanf("%d", &v); V.push_back(v); } sort(V.begin(), V.end(), [&](int a, int b){return S[a] < S[b];}); int high = V[0]; for (int i = 1; i < s; i++) { int lca = LCA(V[i - 1], V[i]); O[lca]--, O[V[i]]++; if (H[lca] < H[high]) H[high]++, H[lca]--, high = lca; } } DFS(1, 1); int ans = 0; vector<int> res; for (int i = 0; i < n - 1; i++) { if (S[E[i].first] > S[E[i].second]) if (O[E[i].first] >= k) ans++, res.push_back(i + 1); if (S[E[i].first] < S[E[i].second]) if (O[E[i].second] >= k) ans++, res.push_back(i + 1); } printf("%d\n", ans); for (int x : res) printf("%d ", x); return 0; }

Compilation message (stderr)

railway.cpp: In function 'int main()':
railway.cpp:39:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |  scanf("%d%d%d", &n, &m, &k);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
railway.cpp:42:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |   int u, v; scanf("%d%d", &u, &v);
      |             ~~~~~^~~~~~~~~~~~~~~~
railway.cpp:50:15: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |   int s; scanf("%d", &s);
      |          ~~~~~^~~~~~~~~~
railway.cpp:55:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |    scanf("%d", &v);
      |    ~~~~~^~~~~~~~~~
#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...