| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 725860 |
2023-04-18T07:52:00 Z |
pavement |
Pastiri (COI20_pastiri) |
C++17 |
|
1000 ms |
278296 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, tot_sz, sz[500005], par[500005], lvl[500005], dep[500005], cl[500005], anc[25][500005], dist_cent[25][500005];
ii o[500005];
vector<int> placed, adj[500005];
unordered_set<int> S[500005];
queue<ii> Q;
void init(int n, int e = -1) {
anc[0][n] = e;
for (int k = 1; k <= 18; 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;
init(u, n);
}
}
int lca(int u, int v) {
if (dep[u] > dep[v]) swap(u, v);
for (int k = 18; k >= 0; k--)
if (dep[v] - (1 << k) >= dep[u]) {
v = anc[k][v];
}
if (u == v) return u;
for (int k = 18; 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)];
}
int get_sz(int n, int e = -1) {
sz[n] = 1;
for (auto u : adj[n]) if (u != e && lvl[u] == -1) {
sz[n] += get_sz(u, n);
}
return sz[n];
}
int cent(int n, int e = -1) {
for (auto u : adj[n]) if (u != e && lvl[u] == -1)
if (tot_sz / 2 < sz[u]) return cent(u, n);
return n;
}
void decomp(int n, int e = -1) {
// find centroid of component containing node n
get_sz(n);
tot_sz = sz[n];
int c = cent(n);
par[c] = e;
if (e != -1) lvl[c] = lvl[e] + 1;
else lvl[c] = 0;
for (auto u : adj[c]) {
if (lvl[u] == -1) decomp(u, c);
}
}
void upd(int u) {
for (int cur = u, k = 0; cur != -1; cur = par[cur], k++) {
S[cur].insert(cl[u] - dist_cent[k][u]);
}
}
bool qry(int u) {
for (int cur = u, k = 0; cur != -1; cur = par[cur], k++) {
if (S[cur].find(dist_cent[k][u]) != S[cur].end()) return 1;
}
return 0;
}
main() {
memset(anc, -1, sizeof anc);
memset(lvl, -1, sizeof lvl);
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);
}
init(1);
decomp(1);
for (int i = 1; i <= N; i++)
for (int cur = i, k = 0; cur != -1; cur = par[cur], k++) {
dist_cent[k][i] = dist(i, cur);
}
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);
}
}
}
sort(o + 1, o + 1 + K, greater<ii>());
return 0;
for (int i = 1; i <= K; i++) {
auto [d, u] = o[i];
if (qry(u)) {
continue;
}
for (int k = 18; k >= 0; k--) {
if (anc[k][u] != -1 && cl[anc[k][u]] == d - dep[anc[k][u]]) {
u = anc[k][u];
}
}
placed.pb(u);
upd(u);
}
cout << placed.size() << '\n';
for (auto u : placed) cout << u << ' ';
cout << '\n';
}
Compilation message
pastiri.cpp:105:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
105 | main() {
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1068 ms |
278296 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
73 ms |
142100 KB |
Unexpected end of file - int32 expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
62 ms |
141516 KB |
Unexpected end of file - int32 expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1092 ms |
171748 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
