제출 #94792

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
94792		shoemakerjo	Cats or Dogs (JOI18_catdog)	C++14	0 / 100	4 ms	2720 KiB

catdog

#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];
};

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]);
		}
	}

	// 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;

	// 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 (myspot[ss] != 1) seg[si].v[1][1] = 0 + ccost[si][1];
		if (myspot[ss] != 2) seg[si].v[0][0] = 0 + ccost[si][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 (myspot[ss] != 1) seg[si].v[1][1] = 0 + ccost[si][1];
		if (myspot[ss] != 2) seg[si].v[0][0] = 0 + ccost[si][0];
		// cout << "updating " << spot << endl;
		// 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(u);
		mat cv = query(nx, 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;
			return min(c0, c1);
		}	
		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

	// cout << "DONE WITH INIT" << endl;
}

int cat(int v) {
	cout << "CAT at " << v  << endl;
	myspot[v] = 1;
 	return uph(v);
}

int dog(int v) {
	cout << "DOG at " << v << endl;
	myspot[v] = 2;
	return uph(v);

}

int neighbor(int v) {
	cout << "EMPTY at " << v << endl;
	myspot[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

• Subtask 1: 0 / 8
• Subtask 2: 0 / 30
• Subtask 3: 0 / 62