| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 594141 |
2022-07-12T06:56:10 Z |
이동현(#8435) |
Unique Cities (JOI19_ho_t5) |
C++17 |
|
164 ms |
20016 KB |
#include <bits/stdc++.h>
using namespace std;
const int NS = (int)2e5 + 4;
int n, m;
vector<int> way[NS];
int col[NS], from[NS];
int ans[NS], online[NS];
int ransval;
pair<int, int> mdis[NS];
int dis[NS];
struct fenw{
int n;
vector<int> tr;
fenw(){}
fenw(int n):n(n + 4){
tr.resize(n);
}
void push(int pos, int val){
pos += 2;
for(int i = pos; i < n; i += (i & -i)){
tr[i] += val;
}
}
int get(int pos){
pos += 2;
int rv = 0;
for(int i = pos; i > 0; i -= (i & -i)){
rv += tr[i];
}
return rv;
}
};
struct seg{
int n;
vector<int> cnt, sum;
seg(){}
void build(int x, int s, int e){
if(s == e){
sum[x] = 1;
return;
}
int m = s + e >> 1;
build(x * 2, s, m), build(x * 2 + 1, m + 1, e);
sum[x] = sum[x * 2] + sum[x * 2 + 1];
}
seg(int n):n(n + 4){
cnt.resize(n * 4);
sum.resize(n * 4);
}
void push(int x, int s, int e, int ps, int pe, int val){
if(pe < s || ps > e){
return;
}
if(ps <= s && pe >= e){
cnt[x] += val;
if(cnt[x]) sum[x] = 0;
else{
if(s == e) sum[x] = 1;
else sum[x] = sum[x * 2] + sum[x * 2 + 1];
}
return;
}
int m = s + e >> 1;
push(x * 2, s, m, ps, pe, val), push(x * 2 + 1, m + 1, e, ps, pe, val);
if(cnt[x]) sum[x] = 0;
else sum[x] = sum[x * 2] + sum[x * 2 + 1];
}
int get(int x, int s, int e, int fs, int fe){
if(fe < s || fs > e || cnt[x]) return 0;
if(fs <= s && fe >= e){
return sum[x];
}
int m = s + e >> 1;
return get(x * 2, s, m, fs, fe) + get(x * 2 + 1, m + 1, e, fs, fe);
}
}tree;
pair<int, int> getfar(int x, int pr = -1){
from[x] = pr;
pair<int, int> rv = {0, x};
for(auto&nxt:way[x]){
if(nxt == pr){
continue;
}
rv = max(rv, getfar(nxt, x));
}
return {rv.first + 1, rv.second};
}
int getdep(int x, int pr = -1){
int rv = 0;
for(auto&nxt:way[x]){
if(online[nxt] || nxt == pr){
continue;
}
dis[nxt] = dis[x] + 1;
rv = max(rv, getdep(nxt, x) + 1);
if(mdis[nxt].first > mdis[x].first) mdis[x].second = mdis[x].first, mdis[x].first = mdis[nxt].first;
else if(mdis[nxt].first > mdis[x].second) mdis[x].second = mdis[nxt].first;
}
return rv;
}
void sol(int x, int pr = -1){
ans[x] += ransval;
if(mdis[x].first){
tree.push(1, 0, n - 1, dis[x] - (mdis[x].first - dis[x]), dis[x] - 1, 1);
}
if(dis[x]) ans[x] += tree.get(1, 0, n - 1, 0, dis[x] - 1);
for(auto&nxt:way[x]){
if(online[nxt] || nxt == pr){
continue;
}
if(mdis[x].first == mdis[nxt].first && mdis[x].first > mdis[x].second){
tree.push(1, 0, n - 1, dis[x] - (mdis[x].first - dis[x]), dis[x] - 1, -1);
if(mdis[x].second) tree.push(1, 0, n - 1, dis[x] - (mdis[x].second - dis[x]), dis[x] - 1, 1);
sol(nxt, x);
if(mdis[x].second) tree.push(1, 0, n - 1, dis[x] - (mdis[x].second - dis[x]), dis[x] - 1, -1);
tree.push(1, 0, n - 1, dis[x] - (mdis[x].first - dis[x]), dis[x] - 1, 1);
}
else{
sol(nxt, x);
}
}
if(mdis[x].first){
tree.push(1, 0, n - 1, dis[x] - (mdis[x].first - dis[x]), dis[x] - 1, -1);
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
tree = seg(n);
tree.build(1, 0, n - 1);
for(int i = 1; i < n; ++i){
int x, y; cin >> x >> y; --x, --y;
way[x].push_back(y);
way[y].push_back(x);
}
int l = getfar(1).second;
int r = getfar(l).second;
vector<int> line;
int now = r;
while(true){
line.push_back(now);
online[now] = 1;
if(from[now] == -1){
break;
}
now = from[now];
}
for(int rep = 0; rep < 2; ++rep){
vector<int> dep((int)line.size()), lpos((int)line.size());
for(int i = 0; i < (int)line.size(); ++i){
dep[i] = getdep(line[i]);
}
vector<int> stk;
for(int i = 0; i < (int)line.size(); ++i){
while((int)stk.size() && stk.back() + dep[stk.back()] < i){
stk.pop_back();
}
if((int)stk.size()){
lpos[i] = stk.back();
}
while((int)stk.size() && stk.back() + dep[stk.back()] <= i + dep[i]){
stk.pop_back();
}
stk.push_back(i);
}
int rpp = (int)line.size() - 1;
fenw rtree((int)line.size() + 4);
for(int i = (int)line.size() / 2 - 1 + rep * ((int)line.size() % 2); i >= 0; --i){
while(rpp > i * 2){
rtree.push(lpos[rpp], 1);
--rpp;
}
ransval = rtree.get(i);
sol(line[i]);
}
reverse(line.begin(), line.end());
}
for(int i = 0; i < n; ++i){
cout << ans[i] << '\n';
}
return 0;
}
Compilation message
joi2019_ho_t5.cpp: In member function 'void seg::build(int, int, int)':
joi2019_ho_t5.cpp:46:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
46 | int m = s + e >> 1;
| ~~^~~
joi2019_ho_t5.cpp: In member function 'void seg::push(int, int, int, int, int, int)':
joi2019_ho_t5.cpp:67:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
67 | int m = s + e >> 1;
| ~~^~~
joi2019_ho_t5.cpp: In member function 'int seg::get(int, int, int, int, int)':
joi2019_ho_t5.cpp:77:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
77 | int m = s + e >> 1;
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
5024 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
5168 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
100 ms |
15944 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
164 ms |
20016 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
5024 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
5168 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
