#include "catdog.h"
#include <bits/stdc++.h>
using namespace std;
int n;
const int maxn = 100010;
const int inf = 1000000000;
int subsize[maxn];
int bigch[maxn];
int myspot[maxn];
int mycol[maxn]; //store the current color of this node
vector<int> preorder; //this is the special preorder thing
vector<int> adj[maxn];
int par[maxn];
int chainhead[maxn]; //pretty sure this is all that matters
//don't need tail??
int chainend[maxn];
int ccost[maxn][2]; //cost of being colored 1 or 2
int pardiff[maxn][2];
struct mat {
int v[2][2];
};
const bool debug = false;
mat seg[maxn*4];
void printmat(mat & thing) {
cout << thing.v[0][0] << ", " << thing.v[0][1] << ", " << thing.v[1][0] <<
", " << thing.v[1][1] << endl;
}
mat merge(mat& a, mat& b) {
//no reason to not pass by reference
mat res;
res.v[0][0] = res.v[0][1] = res.v[1][0] = res.v[1][1] = inf;
for (int i = 0; i <= 1; i++) {
for (int j = 0; j <= 1; j++) {
res.v[i][j] = min(res.v[i][j],
a.v[i][0] + b.v[0][j]);
res.v[i][j] = min(res.v[i][j],
a.v[i][0] + 1 + b.v[1][j]);
res.v[i][j] = min(res.v[i][j],
a.v[i][1] + 1 + b.v[0][j]);
res.v[i][j] = min(res.v[i][j],
a.v[i][1] + b.v[1][j]);
}
}
if (debug) {
cout << " merge of ";
printmat(a);
cout << " and ";
printmat(b);
cout << " produces ";
printmat(res);
}
return res;
}
void predfs(int u, int p = -1) {
par[u] = p;
subsize[u] = 1;
for (int v : adj[u]) {
if (v == p) continue;
predfs(v, u);
subsize[u] += subsize[v];
if (subsize[v] > subsize[bigch[u]]) {
bigch[u] = v;
}
}
}
void dfs(int u) {
preorder.push_back(u);
myspot[u] = preorder.size()-1;
if (par[u] != -1 && bigch[par[u]] == u) {
chainhead[u] = chainhead[par[u]];
}
else chainhead[u] = u;
if (debug) cout << "dfs: " << u << " has head " << chainhead[u] << endl;
chainend[chainhead[u]] = u; //now I am the smallest
if (bigch[u]) {
dfs(bigch[u]);
}
for (int v : adj[u]) {
if (v != bigch[u] && v != par[u]) {
dfs(v);
}
}
}
void buildtree(int ss = 1, int se = n, int si = 0) {
if (ss == se) {
seg[si].v[0][0] = seg[si].v[0][1] = seg[si].v[1][0] = seg[si].v[1][1] = inf;
if (mycol[preorder[ss]] != 1) seg[si].v[1][1] = 0 + ccost[preorder[ss]][1];
if (mycol[preorder[ss]] != 2) seg[si].v[0][0] = 0 + ccost[preorder[ss]][0];
return;
}
int mid = (ss+se)/2;
buildtree(ss, mid, si*2+1);
buildtree(mid+1, se, si*2+2);
seg[si] = merge(seg[si*2+1], seg[si*2+2]);
}
void upd(int spot, int ss = 1, int se = n, int si = 0) {
if (ss == se) {
//update explicitly
seg[si].v[0][0] = seg[si].v[0][1] = seg[si].v[1][0] = seg[si].v[1][1] = inf;
if (mycol[preorder[ss]] != 1) seg[si].v[1][1] = 0 + ccost[preorder[ss]][1];
if (mycol[preorder[ss]] != 2) seg[si].v[0][0] = 0 + ccost[preorder[ss]][0];
if (debug) {
cout << "updating " << spot << endl;
cout << " "; printmat(seg[si]);
}
return;
}
int mid = (ss+se)/2;
if (spot <= mid) upd(spot, ss, mid, si*2+1);
else upd(spot, mid+1, se, si*2+2);
seg[si] = merge(seg[si*2+1], seg[si*2+2]);
}
mat zs; //zeroes
mat query(int qs, int qe, int ss = 1, int se = n, int si = 0) {
if (qs > qe || ss > se || qs > se || qe < ss) return zs;
if (qs <= ss && se <= qe) {
return seg[si];
}
int mid = (ss+se)/2;
mat lhs = query(qs, qe, ss, mid, si*2+1);
mat rhs = query(qs, qe, mid+1, se, si*2+2);
return merge(lhs, rhs);
}
int uph(int u) {
//update up the HLD structure
while (true) { //should return eventually
int nx = chainhead[u];
// cout << u << " goes to " << nx << endl;
upd(myspot[u]);
mat cv = query(myspot[nx], myspot[chainend[nx]]);
int c0 = min(cv.v[0][0], cv.v[0][1]);
int c1 = min(cv.v[1][0], cv.v[1][1]);
if (nx == 1) {
// cout << "THING THING: ";
// printmat(cv);
// cout << c0 << " VVVVV " << c1 << endl;
if (debug) cout << "CCOSTS: " << ccost[1][0] << " -- " << ccost[1][1] << endl;
return min(c0, c1);
}
if (debug) cout << " at " << u << " with " << c0 << " and " << c1 << endl;
if (debug) {
cout << " ";
printmat(cv);
}
int op = par[nx];
ccost[op][0] += min(c0, c1 + 1) - min(pardiff[nx][0], pardiff[nx][1] + 1);
ccost[op][1] += min(c1, c0 + 1) - min(pardiff[nx][1], pardiff[nx][0] + 1);
pardiff[nx][0] = c0;
pardiff[nx][1] = c1;
u = op;
}
}
void initialize(int N, vector<int> A, vector<int> B) {
n = N;
for (int i = 0; i < N-1; i++) {
adj[A[i]].push_back(B[i]);
adj[B[i]].push_back(A[i]);
}
par[1] = -1;
preorder.push_back(-1); //just buffer it so I can one-index
predfs(1);
dfs(1); //this is to get the preorder
// buildtree(); //do not need this because the answer is
zs.v[0][1] = zs.v[1][0] = inf;
// cout << "DONE WITH INIT" << endl;
}
int cat(int v) {
if (debug) cout << "CAT at " << v << endl;
mycol[v] = 1;
return uph(v);
}
int dog(int v) {
if (debug) cout << "DOG at " << v << endl;
mycol[v] = 2;
return uph(v);
}
int neighbor(int v) {
if (debug) cout << "EMPTY at " << v << endl;
mycol[v] = 0;
return uph(v);
}
//THIS IS DONE IN THE WEIRD IOI STYLE
//MUST BE DONE ONLINE
//let's do the HLD thing where ranges are consecutive in a single segment tree
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
4 ms |
2680 KB |
Output is correct |
| 2 |
Correct |
4 ms |
2808 KB |
Output is correct |
| 3 |
Incorrect |
4 ms |
2680 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
4 ms |
2680 KB |
Output is correct |
| 2 |
Correct |
4 ms |
2808 KB |
Output is correct |
| 3 |
Incorrect |
4 ms |
2680 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
4 ms |
2680 KB |
Output is correct |
| 2 |
Correct |
4 ms |
2808 KB |
Output is correct |
| 3 |
Incorrect |
4 ms |
2680 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
