| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 594174 |
2022-07-12T07:39:12 Z |
이동현(#8435) |
Unique Cities (JOI19_ho_t5) |
C++17 |
|
451 ms |
42564 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){
//cout << x << ' ' << s << ' ' << e << ' ' << ps << ' ' << pe << ' ' << val << endl;
if(pe < s || ps > e || ps > pe){
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){
//cout << x << ' ' << s << ' ' << e << ' ' << fs << ' ' << fe << endl;
if(fe < s || fs > e || cnt[x] || fs > fe) 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;
}
if(!mdis[x].first) mdis[x].first = dis[x];
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);
}
for(int i = 0; i < n; ++i){
cin >> col[i];
}
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){
for(int i = 0; i < n; ++i){
dis[i] = 0;
mdis[i] = {0, 0};
}
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){
if(col[1] == 1) ans[i] = !!ans[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:68:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
68 | int m = s + e >> 1;
| ~~^~~
joi2019_ho_t5.cpp: In member function 'int seg::get(int, int, int, int, int)':
joi2019_ho_t5.cpp:79:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
79 | int m = s + e >> 1;
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
5232 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
175 ms |
15628 KB |
Output is correct |
| 2 |
Correct |
131 ms |
26020 KB |
Output is correct |
| 3 |
Correct |
28 ms |
9124 KB |
Output is correct |
| 4 |
Correct |
368 ms |
26484 KB |
Output is correct |
| 5 |
Correct |
309 ms |
41680 KB |
Output is correct |
| 6 |
Correct |
400 ms |
33888 KB |
Output is correct |
| 7 |
Correct |
344 ms |
25888 KB |
Output is correct |
| 8 |
Correct |
451 ms |
28064 KB |
Output is correct |
| 9 |
Correct |
373 ms |
27580 KB |
Output is correct |
| 10 |
Correct |
331 ms |
27468 KB |
Output is correct |
| 11 |
Correct |
169 ms |
26412 KB |
Output is correct |
| 12 |
Correct |
296 ms |
35884 KB |
Output is correct |
| 13 |
Correct |
314 ms |
33784 KB |
Output is correct |
| 14 |
Correct |
376 ms |
33424 KB |
Output is correct |
| 15 |
Correct |
128 ms |
26176 KB |
Output is correct |
| 16 |
Correct |
245 ms |
36832 KB |
Output is correct |
| 17 |
Correct |
294 ms |
34192 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
299 ms |
19608 KB |
Output is correct |
| 2 |
Correct |
267 ms |
40956 KB |
Output is correct |
| 3 |
Correct |
42 ms |
9792 KB |
Output is correct |
| 4 |
Correct |
356 ms |
27164 KB |
Output is correct |
| 5 |
Correct |
265 ms |
42564 KB |
Output is correct |
| 6 |
Correct |
356 ms |
34676 KB |
Output is correct |
| 7 |
Correct |
333 ms |
26680 KB |
Output is correct |
| 8 |
Correct |
342 ms |
30560 KB |
Output is correct |
| 9 |
Correct |
346 ms |
29408 KB |
Output is correct |
| 10 |
Correct |
387 ms |
28572 KB |
Output is correct |
| 11 |
Correct |
269 ms |
26932 KB |
Output is correct |
| 12 |
Correct |
280 ms |
39476 KB |
Output is correct |
| 13 |
Correct |
293 ms |
33884 KB |
Output is correct |
| 14 |
Correct |
317 ms |
33956 KB |
Output is correct |
| 15 |
Correct |
140 ms |
27328 KB |
Output is correct |
| 16 |
Correct |
224 ms |
37596 KB |
Output is correct |
| 17 |
Correct |
338 ms |
34956 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
5232 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
