#include "catdog.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
int n;
const int N = (int)1e5 + 100;
int sub[N];
int par[N];
int link[N];
int sz[N];
vector<int> T[N];
void dfs(int u){
sub[u]=1;
for(auto x : T[u]){
if(x != par[u]){
par[x]=u;
dfs(x);
sub[u] += sub[x];
}
}
}
void make_hld(int u){
for(auto x : T[u]){
if(x != par[u]){
if(sub[x] > sub[u] / 2){
link[x] = link[u];
}
else{
link[x] = x;
}
make_hld(x);
if(sub[x] > sub[u] / 2){
sz[u] = sz[x] + 1;
}
}
}
}
const int inf = (int)1e7 + 1;
struct segment_tree{
struct Node{
int val[2][2];
};
int sz;
vector<Node> TR;
Node unite(Node A, Node B){
Node res;
for(int i = 0 ; i < 2; i ++ ){
for(int j = 0 ; j < 2; j ++ ){
res.val[i][j] = inf;
}
}
for(int p = 0; p < 2; p ++ ){
for(int q = 0; q < 2; q ++ ){
for(int ai = 0; ai < 2; ai ++ ){
for(int bi = 0; bi < 2; bi ++ ){
res.val[p][bi] = min(res.val[p][bi], A.val[p][q] + B.val[ai][bi] + (q != ai));
}
}
}
}
return res;
}
void build(int node, int cl, int cr){
if(node == 1){
sz = cr + 1;
TR.resize(sz * 4 + 16);
}
if(cl == cr){
TR[node].val[0][0] = 0;
TR[node].val[1][1] = 0;
TR[node].val[0][1] = inf;
TR[node].val[1][0] = inf;
return;
}
int mid = (cl + cr) / 2;
build(node * 2, cl, mid);
build(node * 2 + 1, mid + 1, cr);
TR[node] = unite(TR[node * 2], TR[node * 2 + 1]);
}
void sub(int node, int cl, int cr, int id, int mode, int v){
if(cl == cr){
TR[node].val[mode][mode] = v;
return;
}
int mid = (cl + cr) / 2;
if(mid >= id)
sub(node * 2, cl, mid, id, mode, v);
else
sub(node * 2 + 1, mid + 1, cr, id, mode, v);
TR[node] = unite(TR[node * 2], TR[node * 2 + 1]);
}
Node gg;
bool go;
void get(int node, int cl, int cr, int tl, int tr){
if(node==1) go = false;
if(cr < tl || cl > tr) return;
if(cl >= tl && cr <= tr){
if(!go){
gg = TR[node];
}
else{
gg = unite(gg, TR[node]);
}
return;
}
int mid = (cl + cr) / 2;
get(node * 2, cl, mid, tl, tr);
get(node * 2 + 1, mid + 1, cr, tl, tr);
}
void visit(int node, int cl, int cr){
if(cl == cr){
cout << "X: " << TR[node].val[0][0] << " Y: " << TR[node].val[1][1] << "\n";
return;
}
int mid = (cl + cr) / 2;
visit(node * 2, cl, mid);
visit(node * 2 + 1, mid + 1, cr);
}
};
segment_tree chain[N];
int type[N];
ll cx[N];
ll cy[N];
void initialize(int _N, vector<int> A, vector<int> B) {
n = _N;
par[1] = -1;
for(int i = 0 ; i < n - 1; i ++ ){
T[A[i]].push_back(B[i]);
T[B[i]].push_back(A[i]);
}
dfs(1);
link[1] = 1;
make_hld(1);
int pi;
int cur;
for(int i = 1; i <= n; i ++ ){
if(sz[i] == 0){
pi = i;
cur = 0;
while(1){
cur ++ ;
if(pi == link[pi]) break;
pi = par[pi];
}
chain[link[i]].sz = cur;
chain[link[i]].build(1, 0, cur - 1);
}
}
}
void walk(int node){
ll las0, las1;
int nex;
while(1){
nex = par[link[node]];
las0 = min(chain[link[node]].TR[1].val[0][0],chain[link[node]].TR[1].val[1][0]);
las1 = min(chain[link[node]].TR[1].val[0][1],chain[link[node]].TR[1].val[1][1]);
if(nex != -1){
cx[nex] -= min(las0, las1 + 1);
cy[nex] -= min(las1, las0 + 1);
}
if(type[node] == 0){
chain[link[node]].sub(1, 0, chain[link[node]].sz - 1, sz[node], 0, cx[node]);
chain[link[node]].sub(1, 0, chain[link[node]].sz - 1, sz[node], 1, cy[node]);
}
else if(type[node] == 1){
chain[link[node]].sub(1, 0, chain[link[node]].sz - 1, sz[node], 0, cx[node]);
chain[link[node]].sub(1, 0, chain[link[node]].sz - 1, sz[node], 1, inf);
}
else{
chain[link[node]].sub(1, 0, chain[link[node]].sz - 1, sz[node], 1, cy[node]);
chain[link[node]].sub(1, 0, chain[link[node]].sz - 1, sz[node], 0, inf);
}
las0 = min(chain[link[node]].TR[1].val[0][0],chain[link[node]].TR[1].val[1][0]);
las1 = min(chain[link[node]].TR[1].val[0][1],chain[link[node]].TR[1].val[1][1]);
if(nex != -1){
cx[nex] += min(las0, las1 + 1);
cy[nex] += min(las1, las0 + 1);
}
if(nex == -1) break;
node = nex;
}
}
int get(){
int outp = inf;
for(int p = 0 ; p < 2; p ++ ){
for(int q = 0; q < 2; q ++ ){
outp = min(outp, chain[1].TR[1].val[p][q]);
}
}
return outp;
}
int cat(int node) { // set to 0
type[node] = 1;
walk(node);
return get();
}
int dog(int node) { // set to 1
type[node] = 2;
walk(node);
return get();
}
int neighbor(int node) { // any
type[node] = 0;
walk(node);
return get();
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
8140 KB |
Output is correct |
2 |
Correct |
5 ms |
8116 KB |
Output is correct |
3 |
Correct |
5 ms |
8148 KB |
Output is correct |
4 |
Correct |
5 ms |
8140 KB |
Output is correct |
5 |
Correct |
5 ms |
8144 KB |
Output is correct |
6 |
Correct |
5 ms |
8140 KB |
Output is correct |
7 |
Correct |
5 ms |
8144 KB |
Output is correct |
8 |
Correct |
5 ms |
8140 KB |
Output is correct |
9 |
Correct |
5 ms |
8148 KB |
Output is correct |
10 |
Correct |
5 ms |
8148 KB |
Output is correct |
11 |
Correct |
5 ms |
8140 KB |
Output is correct |
12 |
Correct |
5 ms |
8144 KB |
Output is correct |
13 |
Correct |
5 ms |
8140 KB |
Output is correct |
14 |
Correct |
5 ms |
8140 KB |
Output is correct |
15 |
Correct |
5 ms |
8140 KB |
Output is correct |
16 |
Correct |
5 ms |
8140 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
8140 KB |
Output is correct |
2 |
Correct |
5 ms |
8116 KB |
Output is correct |
3 |
Correct |
5 ms |
8148 KB |
Output is correct |
4 |
Correct |
5 ms |
8140 KB |
Output is correct |
5 |
Correct |
5 ms |
8144 KB |
Output is correct |
6 |
Correct |
5 ms |
8140 KB |
Output is correct |
7 |
Correct |
5 ms |
8144 KB |
Output is correct |
8 |
Correct |
5 ms |
8140 KB |
Output is correct |
9 |
Correct |
5 ms |
8148 KB |
Output is correct |
10 |
Correct |
5 ms |
8148 KB |
Output is correct |
11 |
Correct |
5 ms |
8140 KB |
Output is correct |
12 |
Correct |
5 ms |
8144 KB |
Output is correct |
13 |
Correct |
5 ms |
8140 KB |
Output is correct |
14 |
Correct |
5 ms |
8140 KB |
Output is correct |
15 |
Correct |
5 ms |
8140 KB |
Output is correct |
16 |
Correct |
5 ms |
8140 KB |
Output is correct |
17 |
Correct |
7 ms |
8396 KB |
Output is correct |
18 |
Correct |
7 ms |
8412 KB |
Output is correct |
19 |
Correct |
6 ms |
8396 KB |
Output is correct |
20 |
Correct |
6 ms |
8140 KB |
Output is correct |
21 |
Correct |
6 ms |
8268 KB |
Output is correct |
22 |
Correct |
6 ms |
8200 KB |
Output is correct |
23 |
Correct |
7 ms |
8412 KB |
Output is correct |
24 |
Correct |
8 ms |
8396 KB |
Output is correct |
25 |
Correct |
6 ms |
8268 KB |
Output is correct |
26 |
Correct |
6 ms |
8268 KB |
Output is correct |
27 |
Correct |
6 ms |
8148 KB |
Output is correct |
28 |
Correct |
6 ms |
8244 KB |
Output is correct |
29 |
Correct |
7 ms |
8280 KB |
Output is correct |
30 |
Correct |
6 ms |
8148 KB |
Output is correct |
31 |
Correct |
6 ms |
8404 KB |
Output is correct |
32 |
Correct |
6 ms |
8280 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
8140 KB |
Output is correct |
2 |
Correct |
5 ms |
8116 KB |
Output is correct |
3 |
Correct |
5 ms |
8148 KB |
Output is correct |
4 |
Correct |
5 ms |
8140 KB |
Output is correct |
5 |
Correct |
5 ms |
8144 KB |
Output is correct |
6 |
Correct |
5 ms |
8140 KB |
Output is correct |
7 |
Correct |
5 ms |
8144 KB |
Output is correct |
8 |
Correct |
5 ms |
8140 KB |
Output is correct |
9 |
Correct |
5 ms |
8148 KB |
Output is correct |
10 |
Correct |
5 ms |
8148 KB |
Output is correct |
11 |
Correct |
5 ms |
8140 KB |
Output is correct |
12 |
Correct |
5 ms |
8144 KB |
Output is correct |
13 |
Correct |
5 ms |
8140 KB |
Output is correct |
14 |
Correct |
5 ms |
8140 KB |
Output is correct |
15 |
Correct |
5 ms |
8140 KB |
Output is correct |
16 |
Correct |
5 ms |
8140 KB |
Output is correct |
17 |
Correct |
7 ms |
8396 KB |
Output is correct |
18 |
Correct |
7 ms |
8412 KB |
Output is correct |
19 |
Correct |
6 ms |
8396 KB |
Output is correct |
20 |
Correct |
6 ms |
8140 KB |
Output is correct |
21 |
Correct |
6 ms |
8268 KB |
Output is correct |
22 |
Correct |
6 ms |
8200 KB |
Output is correct |
23 |
Correct |
7 ms |
8412 KB |
Output is correct |
24 |
Correct |
8 ms |
8396 KB |
Output is correct |
25 |
Correct |
6 ms |
8268 KB |
Output is correct |
26 |
Correct |
6 ms |
8268 KB |
Output is correct |
27 |
Correct |
6 ms |
8148 KB |
Output is correct |
28 |
Correct |
6 ms |
8244 KB |
Output is correct |
29 |
Correct |
7 ms |
8280 KB |
Output is correct |
30 |
Correct |
6 ms |
8148 KB |
Output is correct |
31 |
Correct |
6 ms |
8404 KB |
Output is correct |
32 |
Correct |
6 ms |
8280 KB |
Output is correct |
33 |
Correct |
204 ms |
26172 KB |
Output is correct |
34 |
Correct |
98 ms |
29384 KB |
Output is correct |
35 |
Correct |
188 ms |
20800 KB |
Output is correct |
36 |
Correct |
326 ms |
39308 KB |
Output is correct |
37 |
Correct |
33 ms |
18052 KB |
Output is correct |
38 |
Correct |
367 ms |
42824 KB |
Output is correct |
39 |
Correct |
348 ms |
42944 KB |
Output is correct |
40 |
Correct |
353 ms |
42932 KB |
Output is correct |
41 |
Correct |
359 ms |
42812 KB |
Output is correct |
42 |
Correct |
352 ms |
42820 KB |
Output is correct |
43 |
Correct |
341 ms |
42968 KB |
Output is correct |
44 |
Correct |
344 ms |
42884 KB |
Output is correct |
45 |
Correct |
340 ms |
42952 KB |
Output is correct |
46 |
Correct |
350 ms |
42800 KB |
Output is correct |
47 |
Correct |
369 ms |
42948 KB |
Output is correct |
48 |
Correct |
98 ms |
38284 KB |
Output is correct |
49 |
Correct |
124 ms |
46260 KB |
Output is correct |
50 |
Correct |
35 ms |
15692 KB |
Output is correct |
51 |
Correct |
53 ms |
23088 KB |
Output is correct |
52 |
Correct |
24 ms |
15836 KB |
Output is correct |
53 |
Correct |
201 ms |
40904 KB |
Output is correct |
54 |
Correct |
118 ms |
22304 KB |
Output is correct |
55 |
Correct |
275 ms |
31932 KB |
Output is correct |
56 |
Correct |
167 ms |
23784 KB |
Output is correct |
57 |
Correct |
247 ms |
38588 KB |
Output is correct |
58 |
Correct |
44 ms |
25044 KB |
Output is correct |
59 |
Correct |
49 ms |
21476 KB |
Output is correct |
60 |
Correct |
107 ms |
41776 KB |
Output is correct |
61 |
Correct |
106 ms |
43200 KB |
Output is correct |
62 |
Correct |
78 ms |
36540 KB |
Output is correct |
63 |
Correct |
71 ms |
18292 KB |
Output is correct |
64 |
Correct |
77 ms |
20252 KB |
Output is correct |
65 |
Correct |
83 ms |
27344 KB |
Output is correct |
66 |
Correct |
91 ms |
12980 KB |
Output is correct |
67 |
Correct |
99 ms |
21712 KB |
Output is correct |
68 |
Correct |
179 ms |
27716 KB |
Output is correct |
69 |
Correct |
46 ms |
10048 KB |
Output is correct |
70 |
Correct |
14 ms |
8448 KB |
Output is correct |
71 |
Correct |
90 ms |
16984 KB |
Output is correct |
72 |
Correct |
121 ms |
24328 KB |
Output is correct |
73 |
Correct |
277 ms |
31056 KB |
Output is correct |
74 |
Correct |
296 ms |
27460 KB |
Output is correct |
75 |
Correct |
218 ms |
30932 KB |
Output is correct |
76 |
Correct |
211 ms |
29636 KB |
Output is correct |
77 |
Correct |
299 ms |
27868 KB |
Output is correct |