#include <bits/stdc++.h>
#define pii pair<int, int>
#define x first
#define y second
using namespace std;
const int INF = 1e9;
const int N = 1e5 + 10;
int n, par[N], rot[N], lev[N], col[N], sz[N], pos[N], dep[N];
pii pv[N];
vector<int> g[N];
struct node {
vector<int> v;
node() {
v = vector<int>( 4, INF );
v[0] = v[3] = 0;
}
friend node operator+( const node &a, const node &b ) {
node ret;
ret.v = vector<int>( 4, INF );
for( int i = 0 ; i < 4 ; i++ ) for( int j = 0 ; j < 4 ; j++ ) {
int bit = ( i&2 ) + ( j&1 );
int dif = ( i&1 ) != ( (j>>1)&1 );
ret.v[bit] = min( ret.v[bit], a.v[i] + b.v[j] + dif );
}
return ret;
}
}t[N*4];
node query( int ll, int rr, int l = 1, int r = n, int idx = 1 ) {
if( l >= ll && r <= rr ) return t[idx];
int mid = l + r >> 1;
if( rr <= mid ) return query( ll, rr, l, mid, idx<<1 );
else if( ll > mid ) return query( ll, rr, mid+1, r, idx<<1|1 );
return query( ll, rr, l, mid, idx<<1 ) + query( ll, rr, mid+1, r, idx<<1|1 );
}
void update( int x, pii k, int l = 1, int r = n, int idx = 1 ) {
if( l == r ) {
t[idx].v[0] += k.x, t[idx].v[3] += k.y;
return ;
}
int mid = l + r >> 1;
if( x <= mid ) update( x, k, l, mid, idx<<1 );
else update( x, k, mid+1, r, idx<<1|1 );
t[idx] = t[idx<<1] + t[idx<<1|1];
}
void build( int l = 1, int r = n, int idx = 1 ) {
if( l == r ) return ;
int mid = l + r >> 1;
build( l, mid, idx<<1 ), build( mid+1, r, idx<<1|1 );
t[idx] = t[idx<<1] + t[idx<<1|1];
}
void updatehld( int u, pii now ) {
while( u ) {
//printf("%d %d\n",now.x,now.y);
update( pos[u], now );
//printf("U %d %d %d\n",u,pos[rot[u]],pos[lev[rot[u]]]);
//node que2 = query( pos[u], pos[u] );
node que = query( pos[rot[u]], pos[lev[rot[u]]] );
//node que3 = query( pos[u], pos[lev[rot[u]]] );
//node que4 = query( pos[lev[rot[u]]], pos[lev[rot[u]]] );
//node que5 = que2 + que4;
/*for( int i = 0 ; i < 4 ; i++ ) printf("%d ",que.v[i]);
printf("\n");
for( int i = 0 ; i < 4 ; i++ ) printf("%d ",que2.v[i]);
printf("\n");
for( int i = 0 ; i < 4 ; i++ ) printf("%d ",que3.v[i]);
printf("\n");
for( int i = 0 ; i < 4 ; i++ ) printf("%d ",que4.v[i]);
printf("\n");
for( int i = 0 ; i < 4 ; i++ ) printf("%d ",que5.v[i]);
printf("\n");*/
int x = min( que.v[0], que.v[1] ), y = min( que.v[2], que.v[3] );
now = pii( min( x, y+1 ), min( x+1, y ) );
//printf("%d %d\n",now.x,now.y);
//printf("%d %d")
pii temp = now;
now.x = now.x - pv[rot[u]].x, now.y = now.y - pv[rot[u]].y;
pv[rot[u]] = temp;
u = par[rot[u]];
}
//printf("NO");
return ;
}
void dfs( int u, int p ) {
sz[u] = 1, par[u] = p, dep[u] = dep[p] + 1;
if( p ) g[u].erase( find( g[u].begin(), g[u].end(), p ) );
for( int &v : g[u] ) {
dfs( v, u );
sz[u] += sz[v];
if( sz[v] > sz[g[u][0]] ) swap( v, g[u][0] );
}
}
void hld( int u ) {
static int idx = 0;
if( !par[u] || u != g[par[u]][0] ) rot[u] = u;
else rot[u] = rot[par[u]];
lev[rot[u]] = u;
pos[u] = ++idx;
for( int v : g[u] ) hld( v );
}
int cat( int u ) {
col[u] = 1;
updatehld( u, pii( 0, INF ) );
//printf("U : %d",u);
node ans = query( pos[rot[1]], pos[lev[1]] );
int ret = INF;
for( int i = 0 ; i < 4 ; i++ ) ret = min( ret, ans.v[i] );
//printf("RET :%d\n",ret);
return ret;
}
int dog( int u ) {
col[u] = 2;
updatehld( u, pii( INF, 0 ) );
node ans = query( pos[rot[1]], pos[lev[1]] );
int ret = INF;
for( int i = 0 ; i < 4 ; i++ ) ret = min( ret, ans.v[i] );
return ret;
}
int neighbor( int u ) {
if( col[u] == 1 ) updatehld( u, pii( 0, -INF ) );
else if( col[u] == 2 ) updatehld( u, pii( -INF, 0 ) );
col[u] = 0;
node ans = query( pos[rot[1]], pos[lev[1]] );
int ret = INF;
for( int i = 0 ; i < 4 ; i++ ) ret = min( ret, ans.v[i] );
return ret;
}
void initialize( int _N, vector<int> A, vector<int> B ) {
n = _N;
for( int i = 0 ; i < n-1 ; i++ ) {
g[A[i]].emplace_back( B[i] );
g[B[i]].emplace_back( A[i] );
}
dfs( 1, 0 ), hld( 1 ), build();
}
/*int main()
{
int n;
vector<int> a, b;
scanf("%d",&n);
for( int i = 1, u, v ; i < n ; i++ ) {
scanf("%d %d",&u,&v);
a.emplace_back( u ), b.emplace_back( v );
}
initialize( n, a, b );
while( 1 ) {
int t, u;
scanf("%d %d",&t,&u);
//printf("WTF");
if( t == 1 ) {
printf("%d\n",cat( u ));
}
else if( t == 2 ) {
printf("%d\n",dog( u ));
}
else {
printf("%d\n",neighbor( u ));
}
}
return 0;
}*/
Compilation message
catdog.cpp: In function 'node query(int, int, int, int, int)':
catdog.cpp:35:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid = l + r >> 1;
~~^~~
catdog.cpp: In function 'void update(int, std::pair<int, int>, int, int, int)':
catdog.cpp:46:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid = l + r >> 1;
~~^~~
catdog.cpp: In function 'void build(int, int, int)':
catdog.cpp:54:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid = l + r >> 1;
~~^~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
31 ms |
24576 KB |
Output is correct |
2 |
Correct |
30 ms |
24576 KB |
Output is correct |
3 |
Correct |
29 ms |
24576 KB |
Output is correct |
4 |
Correct |
30 ms |
24568 KB |
Output is correct |
5 |
Correct |
30 ms |
24576 KB |
Output is correct |
6 |
Correct |
29 ms |
24576 KB |
Output is correct |
7 |
Correct |
30 ms |
24704 KB |
Output is correct |
8 |
Correct |
30 ms |
24576 KB |
Output is correct |
9 |
Correct |
29 ms |
24696 KB |
Output is correct |
10 |
Correct |
31 ms |
24576 KB |
Output is correct |
11 |
Correct |
29 ms |
24704 KB |
Output is correct |
12 |
Correct |
29 ms |
24576 KB |
Output is correct |
13 |
Correct |
31 ms |
24576 KB |
Output is correct |
14 |
Correct |
32 ms |
24568 KB |
Output is correct |
15 |
Correct |
30 ms |
24576 KB |
Output is correct |
16 |
Correct |
29 ms |
24576 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
31 ms |
24576 KB |
Output is correct |
2 |
Correct |
30 ms |
24576 KB |
Output is correct |
3 |
Correct |
29 ms |
24576 KB |
Output is correct |
4 |
Correct |
30 ms |
24568 KB |
Output is correct |
5 |
Correct |
30 ms |
24576 KB |
Output is correct |
6 |
Correct |
29 ms |
24576 KB |
Output is correct |
7 |
Correct |
30 ms |
24704 KB |
Output is correct |
8 |
Correct |
30 ms |
24576 KB |
Output is correct |
9 |
Correct |
29 ms |
24696 KB |
Output is correct |
10 |
Correct |
31 ms |
24576 KB |
Output is correct |
11 |
Correct |
29 ms |
24704 KB |
Output is correct |
12 |
Correct |
29 ms |
24576 KB |
Output is correct |
13 |
Correct |
31 ms |
24576 KB |
Output is correct |
14 |
Correct |
32 ms |
24568 KB |
Output is correct |
15 |
Correct |
30 ms |
24576 KB |
Output is correct |
16 |
Correct |
29 ms |
24576 KB |
Output is correct |
17 |
Correct |
32 ms |
24704 KB |
Output is correct |
18 |
Correct |
33 ms |
24704 KB |
Output is correct |
19 |
Correct |
32 ms |
24704 KB |
Output is correct |
20 |
Correct |
30 ms |
24704 KB |
Output is correct |
21 |
Correct |
30 ms |
24704 KB |
Output is correct |
22 |
Correct |
30 ms |
24704 KB |
Output is correct |
23 |
Correct |
33 ms |
24704 KB |
Output is correct |
24 |
Correct |
33 ms |
24704 KB |
Output is correct |
25 |
Correct |
33 ms |
24696 KB |
Output is correct |
26 |
Correct |
34 ms |
24696 KB |
Output is correct |
27 |
Correct |
29 ms |
24696 KB |
Output is correct |
28 |
Correct |
30 ms |
24704 KB |
Output is correct |
29 |
Correct |
31 ms |
24832 KB |
Output is correct |
30 |
Correct |
30 ms |
24696 KB |
Output is correct |
31 |
Correct |
30 ms |
24704 KB |
Output is correct |
32 |
Correct |
33 ms |
24704 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
31 ms |
24576 KB |
Output is correct |
2 |
Correct |
30 ms |
24576 KB |
Output is correct |
3 |
Correct |
29 ms |
24576 KB |
Output is correct |
4 |
Correct |
30 ms |
24568 KB |
Output is correct |
5 |
Correct |
30 ms |
24576 KB |
Output is correct |
6 |
Correct |
29 ms |
24576 KB |
Output is correct |
7 |
Correct |
30 ms |
24704 KB |
Output is correct |
8 |
Correct |
30 ms |
24576 KB |
Output is correct |
9 |
Correct |
29 ms |
24696 KB |
Output is correct |
10 |
Correct |
31 ms |
24576 KB |
Output is correct |
11 |
Correct |
29 ms |
24704 KB |
Output is correct |
12 |
Correct |
29 ms |
24576 KB |
Output is correct |
13 |
Correct |
31 ms |
24576 KB |
Output is correct |
14 |
Correct |
32 ms |
24568 KB |
Output is correct |
15 |
Correct |
30 ms |
24576 KB |
Output is correct |
16 |
Correct |
29 ms |
24576 KB |
Output is correct |
17 |
Correct |
32 ms |
24704 KB |
Output is correct |
18 |
Correct |
33 ms |
24704 KB |
Output is correct |
19 |
Correct |
32 ms |
24704 KB |
Output is correct |
20 |
Correct |
30 ms |
24704 KB |
Output is correct |
21 |
Correct |
30 ms |
24704 KB |
Output is correct |
22 |
Correct |
30 ms |
24704 KB |
Output is correct |
23 |
Correct |
33 ms |
24704 KB |
Output is correct |
24 |
Correct |
33 ms |
24704 KB |
Output is correct |
25 |
Correct |
33 ms |
24696 KB |
Output is correct |
26 |
Correct |
34 ms |
24696 KB |
Output is correct |
27 |
Correct |
29 ms |
24696 KB |
Output is correct |
28 |
Correct |
30 ms |
24704 KB |
Output is correct |
29 |
Correct |
31 ms |
24832 KB |
Output is correct |
30 |
Correct |
30 ms |
24696 KB |
Output is correct |
31 |
Correct |
30 ms |
24704 KB |
Output is correct |
32 |
Correct |
33 ms |
24704 KB |
Output is correct |
33 |
Correct |
982 ms |
30712 KB |
Output is correct |
34 |
Correct |
292 ms |
30584 KB |
Output is correct |
35 |
Correct |
863 ms |
29552 KB |
Output is correct |
36 |
Correct |
1576 ms |
34784 KB |
Output is correct |
37 |
Correct |
51 ms |
27512 KB |
Output is correct |
38 |
Correct |
1813 ms |
35764 KB |
Output is correct |
39 |
Correct |
1843 ms |
35812 KB |
Output is correct |
40 |
Correct |
1688 ms |
35812 KB |
Output is correct |
41 |
Correct |
1711 ms |
35772 KB |
Output is correct |
42 |
Correct |
1657 ms |
35876 KB |
Output is correct |
43 |
Correct |
1668 ms |
35780 KB |
Output is correct |
44 |
Correct |
1575 ms |
35816 KB |
Output is correct |
45 |
Correct |
1659 ms |
35816 KB |
Output is correct |
46 |
Correct |
1681 ms |
35812 KB |
Output is correct |
47 |
Correct |
1772 ms |
35812 KB |
Output is correct |
48 |
Correct |
484 ms |
32708 KB |
Output is correct |
49 |
Correct |
453 ms |
34720 KB |
Output is correct |
50 |
Correct |
168 ms |
27004 KB |
Output is correct |
51 |
Correct |
189 ms |
28636 KB |
Output is correct |
52 |
Correct |
85 ms |
26616 KB |
Output is correct |
53 |
Correct |
637 ms |
34136 KB |
Output is correct |
54 |
Correct |
486 ms |
29228 KB |
Output is correct |
55 |
Correct |
1805 ms |
32876 KB |
Output is correct |
56 |
Correct |
988 ms |
29980 KB |
Output is correct |
57 |
Correct |
1351 ms |
33968 KB |
Output is correct |
58 |
Correct |
86 ms |
28460 KB |
Output is correct |
59 |
Correct |
179 ms |
28280 KB |
Output is correct |
60 |
Correct |
366 ms |
33528 KB |
Output is correct |
61 |
Correct |
408 ms |
34016 KB |
Output is correct |
62 |
Correct |
238 ms |
31824 KB |
Output is correct |
63 |
Correct |
142 ms |
31228 KB |
Output is correct |
64 |
Correct |
156 ms |
32632 KB |
Output is correct |
65 |
Correct |
152 ms |
36984 KB |
Output is correct |
66 |
Correct |
308 ms |
28152 KB |
Output is correct |
67 |
Correct |
207 ms |
33528 KB |
Output is correct |
68 |
Correct |
468 ms |
37496 KB |
Output is correct |
69 |
Correct |
163 ms |
26104 KB |
Output is correct |
70 |
Correct |
53 ms |
24952 KB |
Output is correct |
71 |
Correct |
212 ms |
30712 KB |
Output is correct |
72 |
Correct |
264 ms |
35704 KB |
Output is correct |
73 |
Correct |
820 ms |
40172 KB |
Output is correct |
74 |
Correct |
873 ms |
37368 KB |
Output is correct |
75 |
Correct |
609 ms |
40056 KB |
Output is correct |
76 |
Correct |
527 ms |
39160 KB |
Output is correct |
77 |
Correct |
921 ms |
37624 KB |
Output is correct |