#include<bits/stdc++.h>
#include "catdog.h"
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/trie_policy.hpp>
#define pb push_back
#define mp make_pair
#define taskname "A"
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> ii;
typedef tree <int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
const int maxn = 1e5 + 5;
const int mod = 1e9 + 7;
int sz[maxn];
int a[maxn];
int n , q;
vector<int> adj[maxn];
int chainhead[maxn];
int chainid[maxn];
int specid[maxn];
int chainsz[maxn];
int par[maxn];
struct seg{
struct node{
int dp[2][2];
int getans(){
int res = 1e5;
for(int i = 0 ; i < 2 ; ++i)for(int j = 0 ; j < 2 ; ++j)res = min(res , dp[i][j]);
return res;
}
friend node operator + (const node & a , const node & b){
node res;
for(int i = 0 ; i < 2 ; ++i)for(int j = 0 ; j < 2 ; ++j){
res.dp[i][j] = 1e5;
for(int k = 0 ; k < 2 ; ++k)for(int t = 0 ; t < 2 ; ++t){
res.dp[i][j] = min(res.dp[i][j] , a.dp[i][k] + b.dp[t][j] + (k ^ t));
}
}
return res;
}
};
vector<node> s;
int n;
void build(int x , int l , int r){
if(l == r){
s[x].dp[0][1] = s[x].dp[1][0] = 1e5;
return;
}
int mid = l + r >> 1;
build(x * 2 , l , mid);build(x * 2 + 1 , mid + 1 , r);
s[x] = s[x * 2] + s[x * 2 + 1];
}
void init(){
s.resize((n + 3) * 4);
build(1,1,n);
}
void update(int x , int &pos , int &delta0 , int &delta1 , int l , int r){
if(l == r){
s[x].dp[0][0] += delta0;
s[x].dp[1][1] += delta1;
return;
}
int mid = l + r >> 1;
if(pos <= mid)update(x * 2 , pos , delta0 , delta1 , l , mid);
else update(x * 2 + 1, pos , delta0 , delta1 , mid + 1 , r);
s[x] = s[x * 2] + s[x * 2 + 1];
}
}s[maxn];
void update(int u , int delta0 , int delta1){
while(u > 0){
int curchain = chainid[u];
auto pre = s[curchain].s[1];
s[curchain].update(1,specid[u],delta0,delta1,1,s[curchain].n);
auto now = s[curchain].s[1];
delta0 = min({now.dp[0][0],now.dp[0][1],now.dp[1][0]+1,now.dp[1][1]+1})
- min({pre.dp[0][0],pre.dp[0][1],pre.dp[1][0]+1,pre.dp[1][1]+1});
delta1 = min({now.dp[0][0] + 1 ,now.dp[0][1] + 1 ,now.dp[1][0],now.dp[1][1]})
- min({pre.dp[0][0] + 1 ,pre.dp[0][1] + 1 ,pre.dp[1][0],pre.dp[1][1]});
u = par[chainhead[curchain]];
}
}
void dfs(int u , int par){
sz[u] = 1;
for(auto c : adj[u]){
if(c == par)continue;
::par[c] = u;
dfs(c , u);
sz[u] += sz[c];
}
}
int nTime = 0;
void hld(int u , int par){
ii best = mp(0,0);
chainid[u] = nTime;
specid[u] = ++s[nTime].n;
if(chainhead[nTime] == 0)chainhead[nTime] = u;
for(auto c : adj[u]){
if(c == par)continue;
best = max(best,mp(sz[c],c));
}
if(best.second != 0)hld(best.second,u);
for(auto c : adj[u]){
if(c == par || c == best.second)continue;
++nTime;
hld(c , u);
}
}
void initialize(int N, vector<int> a, vector<int> b) {
n = N;
for(int i = 0 ; i < n - 1 ; ++i){
adj[a[i]].pb(b[i]);
adj[b[i]].pb(a[i]);
}
for(int i = 1 ; i <= n ; ++i)a[i] = 3;
dfs(1,0);
hld(1,0);
for(int i = 0 ; i <= nTime ; ++i){
s[i].init();
}
}
int cat(int v) {
a[v] = 1;
update(v,1e5,0);
return s[0].s[1].getans();
}
int dog(int v) {
a[v] = 2;
update(v,0,1e5);
return s[0].s[1].getans();
}
int neighbor(int v) {
if(a[v] == 1)update(v,-1e5,0);
else update(v,0,-1e5);
return s[0].s[1].getans();
}
Compilation message
catdog.cpp: In member function 'void seg::build(int, int, int)':
catdog.cpp:60:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid = l + r >> 1;
~~^~~
catdog.cpp: In member function 'void seg::update(int, int&, int&, int&, int, int)':
catdog.cpp:74:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid = l + r >> 1;
~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
5760 KB |
Output is correct |
| 2 |
Correct |
7 ms |
5888 KB |
Output is correct |
| 3 |
Runtime error |
16 ms |
11956 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
5760 KB |
Output is correct |
| 2 |
Correct |
7 ms |
5888 KB |
Output is correct |
| 3 |
Runtime error |
16 ms |
11956 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
5760 KB |
Output is correct |
| 2 |
Correct |
7 ms |
5888 KB |
Output is correct |
| 3 |
Runtime error |
16 ms |
11956 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 4 |
Halted |
0 ms |
0 KB |
- |
