#include "catdog.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
const int inf = 1e9;
int n, a[MAXN];
vector<int> gph[MAXN];
int sz[MAXN], chn[MAXN], csz[MAXN], dfn[MAXN], par[MAXN], piv;
int slack[MAXN][3];
vector<int> line_query(int s, int e){
vector<int> ans(3);
for(int i = e; i >= s; i--){
for(int j = 0; j < 3; j++){
ans[j] += slack[i][j];
}
vector<int> nxt(3);
nxt[0] += min({ans[0] + (a[i] ? inf : 0), ans[1] + 1 + (a[i] == 2 ? inf : 0), ans[2] + 1 + (a[i] == 1 ? inf : 0)});
nxt[1] += min({ans[0] + (a[i] ? inf : 0), ans[1] + 0 + (a[i] == 2 ? inf : 0), ans[2] + 1 + (a[i] == 1 ? inf : 0)});
nxt[2] += min({ans[0] + (a[i] ? inf : 0), ans[1] + 1 + (a[i] == 2 ? inf : 0), ans[2] + 0 + (a[i] == 1 ? inf : 0)});
ans = nxt;
}
return ans;
}
void Do(int v, int w){
for(int i = v; chn[i] != 1; i = par[chn[i]]){
if(par[chn[i]] == 0) break;
auto queryV = line_query(dfn[chn[i]], dfn[chn[i]] + csz[chn[i]] - 1);
int parV = par[chn[i]];
parV = dfn[parV];
slack[parV][0] -= queryV[0];
slack[parV][1] -= queryV[1];
slack[parV][2] -= queryV[2];
}
a[dfn[v]] = w;
for(int i = v; chn[i] != 1; i = par[chn[i]]){
auto queryV = line_query(dfn[chn[i]], dfn[chn[i]] + csz[chn[i]] - 1);
int parV = par[chn[i]];
parV = dfn[parV];
slack[parV][0] += queryV[0];
slack[parV][1] += queryV[1];
slack[parV][2] += queryV[2];
}
}
int cat(int v) {
Do(v, 1);
auto quer = line_query(dfn[1], dfn[1] + csz[1] - 1);
return *min_element(quer.begin(), quer.end());
}
int dog(int v) {
Do(v, 2);
auto quer = line_query(dfn[1], dfn[1] + csz[1] - 1);
return *min_element(quer.begin(), quer.end());
}
int neighbor(int v) {
Do(v, 0);
auto quer = line_query(dfn[1], dfn[1] + csz[1] - 1);
return *min_element(quer.begin(), quer.end());
}
void dfs(int x){
sz[x] = 1;
for(auto &i : gph[x]){
gph[i].erase(find(gph[i].begin(), gph[i].end(), x));
par[i] = x;
dfs(i);
sz[x] += sz[i];
}
sort(gph[x].begin(), gph[x].end(), [&](const int &a, const int &b){
return sz[a] > sz[b];
});
}
void hld(int x){
dfn[x] = ++piv;
csz[chn[x]]++;
if(gph[x].empty()) return;
chn[gph[x][0]] = chn[x];
hld(gph[x][0]);
for(int i=1; i<gph[x].size(); i++){
chn[gph[x][i]] = gph[x][i];
hld(gph[x][i]);
auto q = line_query(dfn[gph[x][i]], dfn[gph[x][i]] + csz[gph[x][i]] - 1);
slack[dfn[x]][0] += q[0];
slack[dfn[x]][1] += q[1];
slack[dfn[x]][2] += q[2];
}
}
void initialize(int N, std::vector<int> A, std::vector<int> B) {
n = N;
for(int i=0; i<n-1; i++){
gph[A[i]].push_back(B[i]);
gph[B[i]].push_back(A[i]);
}
dfs(1);
chn[1] = 1;
hld(1);
}
Compilation message
catdog.cpp: In function 'void hld(int)':
catdog.cpp:86:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=1; i<gph[x].size(); i++){
~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
2688 KB |
Output is correct |
| 2 |
Correct |
5 ms |
2688 KB |
Output is correct |
| 3 |
Incorrect |
5 ms |
2688 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
2688 KB |
Output is correct |
| 2 |
Correct |
5 ms |
2688 KB |
Output is correct |
| 3 |
Incorrect |
5 ms |
2688 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
2688 KB |
Output is correct |
| 2 |
Correct |
5 ms |
2688 KB |
Output is correct |
| 3 |
Incorrect |
5 ms |
2688 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
