Submission #1093138

#TimeUsernameProblemLanguageResultExecution timeMemory
1093138ShadowSharkPastiri (COI20_pastiri)C++17
0 / 100
374 ms184536 KiB
#include <bits/stdc++.h> using namespace std; const int maxN = 5e5 + 5; int depth[maxN], dis[maxN], par[20][maxN], done[maxN]; bool visited[maxN]; vector<int> adj[maxN], save, order[maxN]; void dfs(int u, int pre) { for (auto v: adj[u]) { if (v == pre) continue; depth[v] = depth[u] + 1; par[0][v] = u; dfs(v, u); } } void bfs() { queue<int> Q; for (auto it: save) { visited[it] = true; Q.push(it); } while (Q.size() > 0) { int u = Q.front(); Q.pop(); for (auto v: adj[u]) { if (visited[v]) continue; visited[v] = true; dis[v] = dis[u] + 1; Q.push(v); } } } bool cmp(int u, int v) { return dis[u] < dis[v]; } map<int, int> rem[maxN]; void mark_done(int u) { done[u] = 1; int st = rem[u][dis[u] - 1]; if (st == -1) return ; while (st < adj[u].size() && dis[st] + 1 == dis[u]) { if (!done[adj[u][st]]) mark_done(adj[u][st]); st++; } } int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n, k; cin >> n >> k; for (int i = 1; i < n; i++) { int u, v; cin >> u >> v; adj[u].push_back(v); adj[v].push_back(u); } depth[1] = 1; dfs(1, 1); for (int j = 1; j <= 18; j++) for (int i = 1; i <= n; i++) par[j][i] = par[j - 1][par[j - 1][i]]; for (int i = 1; i <= k; i++) { int x; cin >> x; order[depth[x]].push_back(x); save.push_back(x); } bfs(); for (int i = 1; i <= n; i++) { sort(adj[i].begin(), adj[i].end(), cmp); int pre = -1; for (int id = 0; id < adj[i].size(); id++) if (dis[adj[i][id]] != pre) { pre = dis[adj[i][id]]; rem[i][pre] = id - 1; } } vector<int> ans; for (int dpth = n; dpth >= 1; dpth--) { for (auto it: order[dpth]) { int u = it; if (done[u]) continue; int x = u; for (int j = 18; j >= 0; j--) { int v = par[j][x]; if (v != 0 && depth[u] - depth[v] == dis[v]) x = v; } mark_done(x); ans.push_back(x); } } cout << ans.size() << '\n'; for (auto v: ans) cout << v << ' '; return 0; }

Compilation message (stderr)

pastiri.cpp: In function 'void mark_done(int)':
pastiri.cpp:45:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |     while (st < adj[u].size() && dis[st] + 1 == dis[u]) {
      |            ~~~^~~~~~~~~~~~~~~
pastiri.cpp: In function 'int main()':
pastiri.cpp:86:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |         for (int id = 0; id < adj[i].size(); id++)
      |                          ~~~^~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...