| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 594240 |
2022-07-12T09:13:24 Z |
반딧불(#8432) |
Unique Cities (JOI19_ho_t5) |
C++17 |
|
405 ms |
31276 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct segTree{
int tree[800002];
int lazy[800002];
void propagate(int i, int l, int r){
tree[i] += lazy[i];
if(l!=r){
lazy[i*2] += lazy[i];
lazy[i*2+1] += lazy[i];
}
lazy[i] = 0;
}
void update(int i, int l, int r, int s, int e, int v){
propagate(i, l, r);
if(r<s || e<l) return;
if(s<=l && r<=e){
lazy[i] += v;
return;
}
int m = (l+r)>>1;
update(i*2, l, m, s, e, v);
update(i*2+1, m+1, r, s, e, v);
tree[i] = min(tree[i*2], tree[i*2+1]);
}
int query(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 min(query(i*2, l, m, s, e), query(i*2+1, m+1, r, s, e));
}
} tree;
int n, k, root;
vector<int> link[200002];
int arr[200002];
int ans[200002];
void operate();
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++) scanf("%d", &arr[i]);
operate();
for(int i=1; i<=n; i++){
assert(ans[i] == 0 || ans[i] == 1);
printf("%d\n", ans[i]);
}
}
int par[200002], depth[200002], LCADB[200002][20];
pair<int, int> maxDown[200002][3];
vector<int> dfsFindRootVec;
void dfsFindRoot(int x, int p, int goal, int loc){
dfsFindRootVec.push_back(x);
if(x == goal) root = dfsFindRootVec[loc];
for(auto y: link[x]){
if(y==p) continue;
dfsFindRoot(y, x, goal, loc);
}
dfsFindRootVec.pop_back();
}
void findRoot(){
queue<int> que;
vector<int> dist(n+2, 1e9);
dist[1] = 0, que.push(1);
int last = 0;
while(!que.empty()){
int x = last = que.front(); que.pop();
for(auto y: link[x]){
if(dist[y] != 1e9) continue;
dist[y] = dist[x] + 1;
que.push(y);
}
}
dist = vector<int>(n+2, 1e9);
dist[last] = 0, que.push(last);
int last2 = 0;
while(!que.empty()){
int x = last2 = que.front(); que.pop();
for(auto y: link[x]){
if(dist[y] != 1e9) continue;
dist[y] = dist[x] + 1;
que.push(y);
}
}
dfsFindRoot(last, -1, last2, dist[last2]/2);
}
void dfs(int x, int p=-1){
maxDown[x][0] = make_pair(0, x);
maxDown[x][1] = maxDown[x][2] = make_pair(-1e9, -1);
for(auto y: link[x]){
if(y==p) continue;
par[y] = LCADB[y][0] = x, depth[y] = depth[x]+1;
dfs(y, x);
pair<int, int> tmp (maxDown[y][0].first+1, y);
maxDown[x][2] = tmp;
if(maxDown[x][1] < maxDown[x][2]) swap(maxDown[x][1], maxDown[x][2]);
if(maxDown[x][0] < maxDown[x][1]) swap(maxDown[x][0], maxDown[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] - 2*depth[getLCA(x, y)];
}
int farBelowRoot[200002];
void dfsFar(int x, int p, int fromUp){
farBelowRoot[x] = max(fromUp, maxDown[x][0].first);
for(auto y: link[x]){
if(y==p) continue;
dfsFar(y, x, max(fromUp+1, (maxDown[x][0].second == y ? maxDown[x][1].first : maxDown[x][0].first) + 1));
}
}
void calcRoot(){
map<int, int> mp;
for(int i=1; i<=n; i++){
if(root == i) continue;
mp[depth[i]]++;
}
for(auto x: mp) if(x.second == 1) ans[root] = 1;
}
int s;
int ancesIdx[200002];
void dfsData(int x, int p, vector<int> &v, int anc){
v.push_back(depth[x]);
ancesIdx[x] = anc;
for(auto y: link[x]){
if(y==p) continue;
dfsData(y, x, v, anc);
}
}
struct dat{
int len, imp, idx;
dat(){}
dat(int len, int imp, int idx): len(len), imp(imp), idx(idx){}
bool operator<(const dat &r)const{
return len<r.len;
}
};
dat maxTop[4];
void dfsUpdate(int x, int p, int d){
if(farBelowRoot[x] < d) ans[x] = 1;
for(auto y: link[x]){
if(y==p) continue;
dfsUpdate(y, x, d+1);
}
}
void dfsInside(int x, int p, int d){
if(tree.query(1, 0, n, 0, d-1-max(0, maxDown[x][0].first)) == 0) ans[x] = 1;
for(int i=0; i<2; i++){
if(maxDown[x][i].first >= 1){
// printf("%d %d update: %d~%d\n", x, maxDown[x][i].second, depth[x]-maxDown[x][i].first, depth[x]-1);
tree.update(1, 0, n, depth[x]-maxDown[x][i].first, depth[x]-1, 1);
}
}
for(auto y: link[x]){
if(y==p) continue;
for(int i=0; i<2; i++) if(maxDown[x][i].second == y) tree.update(1, 0, n, depth[x]-maxDown[x][i].first, depth[x]-1, -1);
dfsInside(y, x, d+1);
for(int i=0; i<2; i++) if(maxDown[x][i].second == y) tree.update(1, 0, n, depth[x]-maxDown[x][i].first, depth[x]-1, 1);
}
for(int i=0; i<2; i++){
if(maxDown[x][i].first >= 1){
tree.update(1, 0, n, depth[x]-maxDown[x][i].first, depth[x]-1, -1);
}
}
}
void operate(){
findRoot();
dfs(root);
for(int d=1; d<20; d++) for(int i=1; i<=n; i++) LCADB[i][d] = LCADB[LCADB[i][d-1]][d-1];
for(auto y: link[root]) dfsFar(y, root, 0);
calcRoot();
s = (int)link[root].size();
maxTop[0] = maxTop[1] = maxTop[2] = maxTop[3] = dat(-1e9, -1e9, -1);
for(int i=0; i<s; i++){
int x = link[root][i];
vector<int> v;
dfsData(x, root, v, i);
sort(v.begin(), v.end());
int alone = -1;
for(int j=0; j<(int)v.size(); j++){
if(j+1 < (int)v.size() && v[j] == v[j+1]){
int tmp = j;
while(tmp+1 < (int)v.size() && v[j] == v[tmp+1]) tmp++;
j = tmp;
continue;
}
alone = max(alone, v[j]);
}
dat tmp (v.back(), alone, i);
maxTop[3] = tmp;
if(maxTop[2] < maxTop[3]) swap(maxTop[2], maxTop[3]);
if(maxTop[1] < maxTop[2]) swap(maxTop[1], maxTop[2]);
if(maxTop[0] < maxTop[1]) swap(maxTop[0], maxTop[1]);
}
for(int i=0; i<s; i++){ /// ���� ���� ���� ��
dfsInside(link[root][i], root, 1);
dat mx1 = maxTop[0], mx2 = maxTop[1];
if(mx1.idx == i) mx1 = maxTop[1], mx2 = maxTop[2];
if(mx2.idx == i) mx2 = maxTop[2];
if(mx1.imp <= mx2.len || mx1.imp < 1) continue;
dfsUpdate(link[root][i], root, mx1.imp+1);
}
}
Compilation message
joi2019_ho_t5.cpp: In function 'int main()':
joi2019_ho_t5.cpp:50:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
50 | scanf("%d %d", &n, &k);
| ~~~~~^~~~~~~~~~~~~~~~~
joi2019_ho_t5.cpp:53:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
53 | scanf("%d %d", &x, &y);
| ~~~~~^~~~~~~~~~~~~~~~~
joi2019_ho_t5.cpp:57:34: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
57 | for(int i=1; i<=n; i++) scanf("%d", &arr[i]);
| ~~~~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
5332 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
300 ms |
24000 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
405 ms |
31276 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
5332 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
