| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 485541 |
2021-11-08T05:31:03 Z |
blue |
Pastiri (COI20_pastiri) |
C++17 |
|
1000 ms |
463084 KB |
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <cassert>
using namespace std;
const int maxN = 500'000;
const int INF = 1'000'000'000;
const int logN = 20;
int N, K;
vector<int> edge[1+maxN];
vector<int> sheep_dist(1+maxN, INF);
vector<int> depth(1+maxN, 0);
vector<int> st;
vector<int> limit(1+maxN);
int anc[1+maxN][1+logN];
vector<int> parent(1+maxN);
vector<int> subtree(1+maxN, 1);
void dfs(int u, int p)
{
anc[u][0] = p;
st.push_back(u);
for(int v: edge[u])
{
if(v == p) continue;
depth[v] = 1 + depth[u];
dfs(v, u);
subtree[u] += subtree[v];
}
if(sheep_dist[u] == 0)
{
int lo = 0;
int hi = int(st.size()) - 1;
while(lo != hi)
{
int mid = (lo+hi)/2;
if(sheep_dist[ st[mid] ] < depth[u] - depth[ st[mid] ])
lo = mid+1;
else
hi = mid;
}
limit[u] = st[lo];
// cerr << "shepherd of " << u << " = " << st[lo] << '\n';
}
st.pop_back();
}
int lca(int u, int v)
{
if(depth[u] > depth[v]) swap(u, v);
for(int e = logN; e >= 0; e--)
{
if(depth[v] - (1 << e) >= depth[u])
v = anc[v][e];
}
if(u == v) return u;
for(int e = logN; e >= 0; e--)
{
if(anc[u][e] != anc[v][e])
{
u = anc[u][e];
v = anc[v][e];
}
}
return anc[u][0];
}
int dist(int u, int v)
{
return depth[u] + depth[v] - 2*depth[lca(u,v)];
}
vector<bool> blocked(1+maxN, 0);
vector<int> centroid_parent(1+maxN, 0);
vector<int> parent_dist(1+maxN);
vector< deque< pair<int, int> > > reach_list(1+maxN);
int get_size(int u, int v) // u -> v =
{
if(parent[u] == v)
return N - subtree[u];
else
return subtree[v];
}
vector<bool> reach_visit(1+maxN, 0);
queue<int> tbv;
queue<int> tbvd;
vector<int> last_visit(1+maxN, 0);
void build_centroid(int u)
{
while(1)
{
int next_pos = -1;
for(int v: edge[u])
{
if(blocked[v]) continue;
if(2*get_size(u, v) > N)
{
next_pos = v;
break;
}
}
if(next_pos == -1) break;
u = next_pos;
}
while(!tbv.empty()) tbv.pop();
last_visit[u] = u;
tbv.push(u);
tbvd.push(0);
while(!tbv.empty())
{
int s = tbv.front();
tbv.pop();
int d = tbvd.front();
tbvd.pop();
if(sheep_dist[s] == 0)
reach_list[u].push_back(make_pair(d, s));
for(int t: edge[s])
{
if(blocked[t]) continue;
if(last_visit[t] == u) continue;
last_visit[t] = u;
tbv.push(t);
tbvd.push(d+1);
}
}
blocked[u] = 1;
for(int v: edge[u])
{
if(blocked[v]) continue;
centroid_parent[v] = u;
build_centroid(v);
}
}
vector<int> covered(1+maxN, 0);
void cover_sheep(int u)
{
int d = sheep_dist[u];
int adj = 0;
for(int v = u; v != 0; v = centroid_parent[v])
{
while(1)
{
if(reach_list[v].empty()) break;
if(covered[reach_list[v][0].second])
{
reach_list[v].pop_front();
continue;
}
if(reach_list[v][0].first + adj > d) break;
covered[reach_list[v][0].second] = 1;
reach_list[v].pop_front();
}
adj += parent_dist[v];
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> N >> K;
for(int i = 1; i <= N-1; i++)
{
int u, v;
cin >> u >> v;
edge[u].push_back(v);
edge[v].push_back(u);
}
queue<int> tbv;
for(int k = 1; k <= K; k++)
{
int o;
cin >> o;
tbv.push(o);
sheep_dist[o] = 0;
}
while(!tbv.empty())
{
int u = tbv.front();
tbv.pop();
for(int v: edge[u])
{
if(sheep_dist[v] <= 1 + sheep_dist[u]) continue;
sheep_dist[v] = 1 + sheep_dist[u];
tbv.push(v);
}
}
anc[0][0] = 0;
dfs(1, 0);
for(int e = 1; e <= 20; e++)
for(int u = 0; u <= N; u++)
anc[u][e] = anc[ anc[u][e-1] ][e-1];
for(int i = 1; i <= N; i++) parent[i] = anc[i][0];
build_centroid(1);
// cerr << "C = " << '\n';
// for(int i = 1; i <= N; i++) cerr << i << ' ' << centroid_parent[i] << "\n";
for(int i = 1; i <= N; i++)
{
if(centroid_parent[i] == 0) parent_dist[i] = 0;
else parent_dist[i] = dist(i, centroid_parent[i]);
}
// cerr << "reach list: ";
// for(int i = 1; i <= N; i++)
// {
// cerr << i << ": ";
// for(auto fg: reach_list[i]) cerr << fg.second << "/" << fg.first << " ";
// cerr << "\n";
// }
// cerr << '\n';
vector<int> sheep_pos;
for(int i = 1; i <= N; i++)
if(sheep_dist[i] == 0)
sheep_pos.push_back(i);
sort(sheep_pos.begin(), sheep_pos.end(), [] (int f, int g)
{
return depth[f] > depth[g];
});
vector<int> res;
// assert(int(sheep_pos.size()) <= 15);
for(int s: sheep_pos)
{
if(covered[s]) continue;
int t = limit[s];
res.push_back(t);
cover_sheep(t);
// for(int i: sheep_pos)
// {
// if(covered[i]) continue;
//
// if(dist(t, i) == depth[s] - depth[t])
// covered[i] = 1;
// }
}
cout << (int)res.size() << '\n';
for(int r: res) cout << r << ' ';
cout << "\n";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1122 ms |
463084 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
196 ms |
367044 KB |
Output is correct |
| 2 |
Correct |
185 ms |
366984 KB |
Output is correct |
| 3 |
Execution timed out |
1120 ms |
431696 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
190 ms |
366660 KB |
Output is correct |
| 2 |
Correct |
180 ms |
366588 KB |
Output is correct |
| 3 |
Correct |
184 ms |
366660 KB |
Output is correct |
| 4 |
Correct |
182 ms |
366604 KB |
Output is correct |
| 5 |
Correct |
211 ms |
367428 KB |
Output is correct |
| 6 |
Correct |
184 ms |
366800 KB |
Output is correct |
| 7 |
Correct |
191 ms |
366660 KB |
Output is correct |
| 8 |
Correct |
185 ms |
366656 KB |
Output is correct |
| 9 |
Correct |
181 ms |
366660 KB |
Output is correct |
| 10 |
Correct |
183 ms |
366592 KB |
Output is correct |
| 11 |
Correct |
190 ms |
366592 KB |
Output is correct |
| 12 |
Correct |
186 ms |
366588 KB |
Output is correct |
| 13 |
Correct |
186 ms |
366592 KB |
Output is correct |
| 14 |
Correct |
234 ms |
367876 KB |
Output is correct |
| 15 |
Correct |
210 ms |
366916 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1115 ms |
431192 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
