제출 #94799

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
94799		shoemakerjo	Cats or Dogs (JOI18_catdog)	C++14	100 / 100	598 ms	22848 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];
};

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;
	if (debug) cout << u << " has parent " << p << endl;
	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) {
	//pretty sure this is a useless method

	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;

	if (qs > mid) {
		return query(qs, qe, mid+1, se, si*2+2);
	}
	if (qe <= mid) {
		return query(qs, qe, ss, mid, si*2+1);
	}

	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
	// if (debug) cout << "start of an HLD trek: ";

	while (true) { //should return eventually
		int nx = chainhead[u];


		// cout << u << " goes to " << nx << endl;

		upd(myspot[u]);

		if (debug) {
			cout << "      " << u << " :: " << ccost[u][0] << " - " << ccost[u][1] << endl;
			mat cccc = query(myspot[u], myspot[u]);
			cout << "     "; printmat(cccc) ;	
		}

		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 (debug) cout << u << " ";

		if (nx == 1) {

			// cout << "THING THING: ";
			// printmat(cv);
			// if (debug) cout << 1 << endl;
			if (debug) 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;

	if (debug) uph(v);

	if (debug) {
		for (int i = 1; i <= n; i++) {
			cout << i << " ::: ";
			mat cc = query(myspot[i], myspot[i]);
			printmat(cc);
		}
	}

	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

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