| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 746757 |
2023-05-23T03:58:09 Z |
pavement |
Pastiri (COI20_pastiri) |
C++17 |
|
1000 ms |
190028 KB |
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define int long long
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define ppb pop_back
#define eb emplace_back
#define g0(a) get<0>(a)
#define g1(a) get<1>(a)
#define g2(a) get<2>(a)
#define g3(a) get<3>(a)
#define g4(a) get<4>(a)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
using db = double;
using ll = long long;
using ld = long double;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;
using iiii = tuple<int, int, int, int>;
using iiiii = tuple<int, int, int, int, int>;
template<class key, class value = null_type, class cmp = less<key> >
using ordered_set = tree<key, value, cmp, rb_tree_tag, tree_order_statistics_node_update>;
int N, K, idx, pre[500005], sz[500005], dep[500005], cl[500005], to[500005], to2[500005], ft[500005], anc[25][500005];
ii o[500005];
vector<int> placed, adj[500005];
queue<ii> Q;
int ls(int x) { return x & -x; }
void upd(int p, int v) {
for (; p <= N; p += ls(p)) ft[p] += v;
}
int qry(int p) {
int r = 0;
for (; p; p -= ls(p)) r += ft[p];
return r;
}
int dfs(int n, int e = -1) {
pre[n] = ++idx;
sz[n] = 1;
anc[0][n] = e;
for (int k = 1; k <= 20; k++) {
if (anc[k - 1][n] == -1) break;
anc[k][n] = anc[k - 1][anc[k - 1][n]];
}
for (auto u : adj[n]) if (u != e) {
dep[u] = dep[n] + 1;
sz[n] += dfs(u, n);
}
return sz[n];
}
int lca(int u, int v) {
if (dep[u] > dep[v]) swap(u, v);
for (int k = 20; k >= 0; k--)
if (dep[v] - (1 << k) >= dep[u]) {
v = anc[k][v];
}
if (u == v) return u;
for (int k = 20; k >= 0; k--)
if (anc[k][u] != anc[k][v]) {
u = anc[k][u];
v = anc[k][v];
}
return anc[0][u];
}
int dist(int u, int v) {
return dep[u] + dep[v] - 2 * dep[lca(u, v)];
}
main() {
memset(anc, -1, sizeof anc);
ios::sync_with_stdio(0);
cin.tie(0);
cin >> N >> K;
for (int i = 1, u, v; i < N; i++) {
cin >> u >> v;
adj[u].pb(v);
adj[v].pb(u);
}
dfs(1);
for (int i = 1; i <= N; i++) {
cl[i] = (int)1e9;
}
for (int i = 1; i <= K; i++) {
cin >> o[i].second;
o[i].first = dep[o[i].second];
Q.emplace(0, o[i].second);
cl[o[i].second] = 0;
}
while (!Q.empty()) {
auto [d, u] = Q.front();
Q.pop();
if (d != cl[u]) continue;
for (auto v : adj[u]) {
if (cl[v] > d + 1) {
cl[v] = d + 1;
Q.emplace(cl[v], v);
}
}
}
for (int i = 1; i <= N; i++) {
int u = i;
for (int k = 20; k >= 0; k--) {
if (anc[k][u] != -1 && cl[anc[k][u]] == dep[i] - dep[anc[k][u]]) {
u = anc[k][u];
}
}
to[i] = u;
u = i;
for (int k = 20; k >= 0; k--) {
if (min(cl[i], dep[i]) & (1 << k)) {
u = anc[k][u];
}
}
to2[i] = u;
}
sort(o + 1, o + 1 + K, greater<ii>());
for (int i = 1; i <= K; i++) {
auto [d, u] = o[i];
if (qry(pre[to[u]] + sz[to[u]] - 1) - qry(pre[to[u]] - 1)) continue;
placed.pb(to[u]);
upd(pre[u], 1);
if (anc[0][pre[to2[to[u]]]] != -1) upd(anc[0][pre[to2[to[u]]]], -1);
}
cout << placed.size() << '\n';
for (auto u : placed) cout << u << ' ';
cout << '\n';
}
Compilation message
pastiri.cpp:79:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
79 | main() {
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
298 ms |
187004 KB |
Output is correct |
| 2 |
Incorrect |
330 ms |
190028 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
47 ms |
110412 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
47 ms |
110140 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1034 ms |
163584 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
