#include "catdog.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll LIM = 1e18;
struct Matrix{
ll mat[3][3];
Matrix(){
for(int i=0; i<9; i++) mat[i/3][i%3] = 0;
}
Matrix(vector<ll> vec){
for(int i=0; i<9; i++) mat[i/3][i%3] = vec[i];
}
Matrix operator+(const vector<ll> &r)const{
Matrix ret;
for(int i=0; i<3; i++) for(int j=0; j<3; j++) ret.mat[i][j] = mat[i][j] + r[j];
return ret;
}
Matrix operator*(const Matrix &r)const{
Matrix ret;
for(int a=0; a<3; a++){
for(int b=0; b<3; b++){
ret.mat[a][b] = LIM;
for(int c=0; c<3; c++){
ret.mat[a][b] = min(ret.mat[a][b], mat[a][c] + r.mat[c][b]);
}
}
}
return ret;
}
vector<ll> render()const{
vector<ll> ret (3, LIM);
for(int i=0; i<3; i++) for(int j=0; j<3; j++) ret[j] = min(ret[j], mat[i][j]);
return ret;
}
};
struct segTree{
Matrix tree[400002];
segTree(){}
void update(int i, int l, int r, int x, Matrix &val){
if(l==r){
for(int j=0; j<3; j++) for(int k=0; k<3; k++) tree[i] = val;
return;
}
int m = (l+r)>>1;
if(x <= m) update(i*2, l, m, x, val);
else update(i*2+1, m+1, r, x, val);
tree[i] = tree[i*2] * tree[i*2+1];
}
Matrix query(int i, int l, int r, int s, int e){
if(s<=l && r<=e) return tree[i];
int m = (l+r)>>1;
if(e<=m) return query(i*2, l, m, s, e);
if(m<s) return query(i*2+1, m+1, r, s, e);
return query(i*2, l, m, s, e) * query(i*2+1, m+1, r, s, e);
}
} tree;
int n;
int x;
int arr[100002];
vector<int> link[100002];
ll DP[100002][3];
int in[100002], top[100002], idx[100002], sz[100002], depth[100002], par[100002], tail[100002], inCnt;
void dfs_sz(int x, int p=-1){
if(p!=-1) link[x].erase(find(link[x].begin(), link[x].end(), p));
sz[x] = 1;
for(auto &y: link[x]){
depth[y] = depth[x] + 1;
par[y] = x;
dfs_sz(y, x);
sz[x] += sz[y];
if(sz[y] > sz[link[x][0]]) swap(y, link[x][0]);
}
}
void dfs_hld(int x){
in[x] = ++inCnt;
idx[in[x]] = x;
for(auto y: link[x]){
top[y] = y == link[x][0] ? top[x] : y;
dfs_hld(y);
}
}
Matrix cost[100002];
Matrix sum[100002];
vector<ll> slack[100002];
const Matrix preset[3] = {
Matrix ({0, 0, 0, 1, 0, 1, 1, 1, 0}),
Matrix ({LIM, 0, LIM, LIM, 0, LIM, LIM, 1, LIM}),
Matrix ({LIM, LIM, 0, LIM, LIM, 1, LIM, LIM, 0})
};
void initialize(int N, vector<int> A, vector<int> B){
n = N;
for(int i=0; i<n-1; i++){
link[A[i]].push_back(B[i]);
link[B[i]].push_back(A[i]);
}
dfs_sz(1);
top[1] = 1;
dfs_hld(1);
for(int i=1; i<=n; i++){
cost[i] = sum[i] = preset[0];
tree.update(1, 1, n, in[i], cost[i]);
slack[i].resize(3);
if(in[i] > in[tail[top[i]]]) tail[top[i]] = i;
}
}
int change(int, int);
int cat(int v){
return change(v, 1);
}
int dog(int v) {
return change(v, 2);
}
int neighbor(int v){
return change(v, 3);
}
vector<ll> upgrade(vector<ll> vec){
vector<ll> ret {min({vec[0], vec[1]+1, vec[2]+1}), min({vec[0], vec[1], vec[2]+1}), min({vec[0], vec[1]+1, vec[2]})};
return ret;
}
int change(int v, int to){
cost[v] = preset[to];
vector<ll> vec;
int x = v;
while(x){
int p = par[top[x]];
int s = in[top[x]];
int e = in[tail[top[x]]];
vec = upgrade(tree.query(1, 1, n, s, e).render());
if(p) for(int j=0; j<3; j++) slack[p][j] -= vec[j];
sum[x] = cost[x] + slack[x];
tree.update(1, 1, n, in[x], sum[x]);
vec = upgrade(tree.query(1, 1, n, s, e).render());
if(p) for(int j=0; j<3; j++) slack[p][j] += vec[j];
x = p;
}
int s2 = 1, e2 = in[tail[1]];
vector<ll> tmp = tree.query(1, 1, n, s2, e2).render();
return *min_element(tmp.begin(), tmp.end());
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
23 ms |
47308 KB |
Output is correct |
2 |
Incorrect |
24 ms |
47268 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
23 ms |
47308 KB |
Output is correct |
2 |
Incorrect |
24 ms |
47268 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
23 ms |
47308 KB |
Output is correct |
2 |
Incorrect |
24 ms |
47268 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |