| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 412101 |
2021-05-26T13:56:43 Z |
반딧불(#7584) |
Pastiri (COI20_pastiri) |
C++17 |
|
760 ms |
134124 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct Fenwick{
int n;
int tree[500002];
void add(int x, int y){
while(x){
tree[x] += y;
x -= x&-x;
}
}
int get(int x){
int ret = 0;
while(x<=n){
ret += tree[x];
x += x&-x;
}
return ret;
}
} tree;
struct segTree{
int tree[2000002], lazy[2000002]; /// a a+2 a+4 ... ���·� ������ ���̴�.
void init(int i, int l, int r){
tree[i] = lazy[i] = -1e9;
if(l==r) return;
int m = (l+r)>>1;
init(i*2, l, m), init(i*2+1, m+1, r);
}
void propagate(int i, int l, int r){
tree[i] = max(tree[i], lazy[i] + 2*(r-l));
if(l!=r){
int m = (l+r)>>1;
lazy[i*2] = max(lazy[i*2], lazy[i]);
lazy[i*2+1] = max(lazy[i*2+1], lazy[i] + 2*(m+1-l));
}
lazy[i] = -1e9;
}
void update(int i, int l, int r, int s, int e, int x){
propagate(i, l, r);
if(r<s || e<l) return;
if(s<=l && r<=e){
lazy[i] = max(lazy[i], x);
propagate(i, l, r);
return;
}
int m = (l+r)>>1;
update(i*2, l, m, s, e, x);
update(i*2+1, m+1, r, s, e, x + 2*(m+1-l));
tree[i] = max(tree[i*2], tree[i*2+1]);
}
int getVal(int i, int l, int r, int s, int e){
propagate(i, l, r);
if(r<s || e<l) return -1e9;
if(s<=l && r<=e) return tree[i];
int m = (l+r)>>1;
return max(getVal(i*2, l, m, s, e), getVal(i*2+1, m+1, r, s, e));
}
} sgtree;
int n, k;
int par[500002], LCADB[500002][20];
vector<int> link[500002];
int minDist[500002], depth[500002];
int in[500002], idx[500002], sz[500002], top[500002], inCnt;
vector<int> loc;
int ans;
int ansX[500002], ansY[500002];
void dfs_first(int x, int p=-1){
if(p != -1) link[x].erase(find(link[x].begin(), link[x].end(), p));
sz[x] = 1;
for(auto &y: link[x]){
if(y == p) continue;
par[y] = x;
depth[y] = depth[x]+1;
dfs_first(y, x);
minDist[x] = min(minDist[x], minDist[y]+1);
sz[x] += sz[y];
if(sz[link[x][0]] < sz[y]) swap(link[x][0], y);
}
}
void dfs_second(int x, int p=-1, int fromUp=1e9){
minDist[x] = min(minDist[x], fromUp);
in[x] = ++inCnt;
idx[in[x]] = x;
for(auto y: link[x]){
if(y == p) continue;
if(link[x][0] == y) top[y] = top[x];
else top[y] = y;
dfs_second(y, x, minDist[x]+1);
}
}
int getLCA(int x, int y){
if(depth[x] > depth[y]) swap(x, y);
for(int d=0; d<20; d++) if((depth[y] - depth[x]) & (1<<d)) y = LCADB[y][d];
if(x==y) return x;
for(int d=19; d>=0; d--) if(LCADB[x][d] != LCADB[y][d]) x = LCADB[x][d], y = LCADB[y][d];
return par[x];
}
int dist(int x, int y){
return depth[x] + depth[y] - depth[getLCA(x, y)] * 2;
}
bool already(int x){
if(tree.get(in[x])) return true;
int tDepth = depth[x];
while(x){
if(tDepth <= sgtree.getVal(1, 1, n, in[top[x]], in[x])) return true;
x = par[top[x]];
}
return false;
}
int main(){
scanf("%d %d", &n, &k);
for(int i=1; i<n; i++){
int x, y;
scanf("%d %d", &x, &y);
link[x].push_back(y), link[y].push_back(x);
}
for(int i=1; i<=n; i++) minDist[i] = 1e9;
for(int i=1; i<=k; i++){
int x;
scanf("%d", &x);
minDist[x] = 0;
loc.push_back(x);
}
dfs_first(1);
top[1] = 1;
dfs_second(1);
for(int i=1; i<=n; i++) LCADB[i][0] = par[i];
for(int d=1; d<20; d++) for(int i=1; i<=n; i++) LCADB[i][d] = LCADB[LCADB[i][d-1]][d-1];
tree.n = n;
sgtree.init(1, 1, n);
sort(loc.begin(), loc.end(), [&](int x, int y){
return depth[x] > depth[y];
});
for(int i=0; i<k; i++){
int p = loc[i];
if(already(p)) continue;
int targ = p, cnt = 0;
for(int d=19; d>=0; d--){
if(LCADB[targ][d] == 0) continue;
int p2 = LCADB[targ][d];
if(depth[p] - depth[p2] == minDist[p2]) targ = p2, cnt += (1<<d);
}
tree.add(in[targ] + sz[targ] - 1, 1);
tree.add(in[targ] - 1, -1);
ansX[ans] = targ;
ans++;
int fDepth = depth[targ];
while(targ){
int tp = top[targ];
if(depth[targ] < fDepth-cnt) break;
sgtree.update(1, 1, n, in[tp], in[targ], 2 * depth[tp] + cnt - fDepth);
targ = par[tp];
}
}
printf("%d\n", ans);
for(int i=0; i<ans; i++) printf("%d ", ansX[i]);
}
Compilation message
pastiri.cpp: In function 'int main()':
pastiri.cpp:129:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
129 | scanf("%d %d", &n, &k);
| ~~~~~^~~~~~~~~~~~~~~~~
pastiri.cpp:132:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
132 | scanf("%d %d", &x, &y);
| ~~~~~^~~~~~~~~~~~~~~~~
pastiri.cpp:138:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
138 | scanf("%d", &x);
| ~~~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
345 ms |
128416 KB |
Output is correct |
| 2 |
Correct |
377 ms |
130120 KB |
Output is correct |
| 3 |
Correct |
339 ms |
130192 KB |
Output is correct |
| 4 |
Correct |
687 ms |
134124 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
13004 KB |
Sheep 4257 not protected |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
12380 KB |
Sheep 12 not protected |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
760 ms |
92064 KB |
Sheep 54 not protected |
| 2 |
Halted |
0 ms |
0 KB |
- |
