Submission #645710

#	Time	Username	Problem	Language	Result	Execution time	Memory
645710		khshg	Cats or Dogs (JOI18_catdog)	C++14	0 / 100	1 ms	2644 KiB

catdog

#include<bits/stdc++.h>

using namespace std;

const int maxn=100010;
int N, par[maxn], sz[maxn];
int pos[maxn], _Time, flat[maxn], anc[maxn];
int ans;
bool hut[maxn];
vector<int> A, B, adj[maxn];

struct segment_tree {
	int loc;
	array<int, 2> stat, lazy;
} st[4*maxn];

void dfs_sz(int s, int p) {
	sz[s] = 1;
	par[s] = p;
	if(int(adj[s].size()) >= 2 && adj[s][0] == p)
		swap(adj[s][0], adj[s][1]);
	for(int& u : adj[s]) {
		if(u != p) {
			dfs_sz(u, s);
			sz[s] += sz[u];
			if(sz[u] > sz[adj[s][0]])
				swap(u, adj[s][0]);
		}
	}
}

void build_hld(int s) {
	pos[s] = _Time;
	flat[_Time] = s;
	++_Time;
	for(int& u : adj[s]) {
		if(u != par[s]) {
			if(u == adj[s][0])
				anc[u] = anc[s];
			else
				anc[u] = u;
			build_hld(u);
		}
	}
}

int LCA(int u, int v) {
	if(pos[u] < pos[v])
		swap(u, v);
	if(anc[u] == anc[v])
		return v;
	return LCA(par[anc[u]], v);
}

void build_st(int v, int tl, int tr) {
	if(tl == tr) {
		st[v].loc = -1;
		st[v].stat[0] = st[v].stat[1] = 0;
		st[v].lazy[0] = st[v].lazy[1] = 0;
		return;
	}
	int tm = (tl + tr) / 2;
	build_st(2 * v + 1, tl, tm);
	build_st(2 * v + 2, tm + 1, tr);
	st[v].loc = -1;
	st[v].stat[0] = st[v].stat[1] = 0;
	st[v].lazy[0] = st[v].lazy[1] = 0;
}

void initialize(int _N, vector<int> _A, vector<int> _B) {
	swap(N, _N);
	swap(A, _A);
	swap(B, _B);
	for (int i = 0; i <= N-2; ++i) {
		--A[i];
		--B[i];
		adj[A[i]].push_back(B[i]);
		adj[B[i]].push_back(A[i]);
	}
	dfs_sz(0, -1);
	build_hld(0);
	build_st(0, 0, N-1);
}

void flip(int v, int tl, int tr, int ind) {
	if(tl == tr) {
		if(st[v].loc == -1)
			st[v].loc = flat[tl];
		else
			st[v].loc = -1;
		return;
	}
	int tm = (tl + tr) / 2;
	if(ind <= tm)
		flip(2 * v + 1, tl, tm, ind);
	else
		flip(2 * v + 2, tm + 1, tr, ind);
	st[v].loc = st[2 * v + 2].loc;
	if(st[v].loc == -1)
		st[v].loc = st[2 * v + 1].loc;
}

void flip(int s) {
	flip(0, 0, N - 1, pos[s]);
}

int get_loc(int v, int tl, int tr, int l, int r) {
	if(tl == l && tr == r)
		return st[v].loc;
	int tm = (tl + tr) / 2;
	if(r <= tm)
		return get_loc(2 * v + 1, tl, tm, l, r);
	if(l > tm)
		return get_loc(2 * v + 2, tm + 1, tr, l, r);
	int T = get_loc(2 * v + 2, tm + 1, tr, tm + 1, r);
	if(T != -1)
		return T;
	return get_loc(2 * v + 1, tl, tm, l, tm);
}

int get_loc(int s) {
	int res = get_loc(0, 0, N - 1, pos[anc[s]], pos[s]);
	if(res != -1)
		return res;
	if(!anc[s])
		return -1;
	return get_loc(par[anc[s]]);
}

void push_down(int v) {
	st[2 * v + 1].stat[0] += st[v].lazy[0];
	st[2 * v + 1].stat[1] += st[v].lazy[1];
	st[2 * v + 2].stat[0] += st[v].lazy[0];
	st[2 * v + 2].stat[1] += st[v].lazy[1];
	st[2 * v + 1].lazy[0] += st[v].lazy[0];
	st[2 * v + 1].lazy[1] += st[v].lazy[1];
	st[2 * v + 2].lazy[0] += st[v].lazy[0];
	st[2 * v + 2].lazy[1] += st[v].lazy[1];
	st[v].lazy[0] = st[v].lazy[1] = 0;
}

array<int, 2> val(int v, int tl, int tr, int ind) {
	if(tl == tr)
		return st[v].stat;
	push_down(v);
	int tm = (tl + tr) / 2;
	if(ind <= tm)
		return val(2  * v + 1, tl, tm, ind);
	return val(2 * v + 2, tm + 1, tr, ind);
}

array<int, 2> val(int s) {
	return val(0, 0, N - 1, pos[s]);
}

void add(int v, int tl, int tr, int l, int r, array<int, 2> a) {
	if(tl == l && tr == r) {
		st[v].stat[0] += a[0];
		st[v].stat[1] += a[1];
		st[v].lazy[0] += a[0];
		st[v].lazy[1] += a[1];
		return;
	}
	push_down(v);
	int tm = (tl + tr) / 2;
	if(r <= tm)
		add(2 * v + 1, tl, tm, l, r, a);
	else if(l > tm)
		add(2 * v + 2, tm+1, tr, l, r, a);
	else {
		add(2 * v + 1, tl, tm, l, tm, a);
		add(2 * v + 2, tm + 1, tr, tm + 1, r, a);
	}
	st[v].stat[0] = st[2 * v + 1].stat[0] + st[2 * v + 2].stat[0];
	st[v].stat[1] = st[2 * v + 1].stat[1] + st[2 * v + 2].stat[1];
}

void add(int s, int p, array<int, 2> a) {
	while(anc[p] != anc[s]) {
		add(0, 0, N - 1, pos[anc[s]], pos[s], a);
		s = par[anc[s]];
	}
	add(0, 0, N - 1, pos[p], pos[s], a);
}

int cat(int v) {
	--v;
	flip(v);
	hut[v]=0;
	if(!v) {
		array<int, 2> K = val(0);
		ans -= min(K[0], K[1]);
		ans += K[1];
		return ans;
	}
	int O = get_loc(par[v]);
	if(O == -1) {
		array<int, 2> K = val(0), C = val(v);
		ans -= min(K[0], K[1]);
		add(par[v], 0, array<int, 2>{-C[0] + 1, -C[1]});
		K = val(0);
		ans += min(K[0], K[1]) + C[1];
		return ans;
	}
	array<int, 2> C = val(v);
	add(par[v], O, array<int, 2>{-C[0] + 1, -C[1]});
	if(hut[O])
		ans += C[1] - C[0] + 1;
	return ans;
}

int dog(int v) {
	--v;
	flip(v);
	hut[v]=1;
	if(!v) {
		array<int, 2> K = val(0);
		ans -= min(K[0], K[1]);
		ans += K[0];
		return ans;
	}
	int O = get_loc(par[v]);
	if(O == -1) {
		array<int, 2> K = val(0), C = val(v);
		ans -= min(K[0], K[1]);
		add(par[v], 0, array<int, 2>{-C[0], -C[1] + 1});
		K = val(0);
		ans += min(K[0], K[1]) + C[0];
		return ans;
	}
	array<int, 2> C = val(v);
	add(par[v], O, array<int, 2>{-C[0], -C[1] + 1});
	if(!hut[O])
		ans += C[0] - C[1] + 1;
	return ans;
}

int neighbor(int v) {
	--v;
	flip(v);
	array<int, 2> C = val(v);
	ans -= C[(hut[v] ^ 1)];
	if(!v) {
		ans += min(C[0], C[1]);
		return ans;
	}
	int O = get_loc(par[v]);
	if(O == -1) {
		array<int, 2> K = val(0);
		ans -= min(K[0], K[1]);
		add(par[v], 0, array<int, 2>{C[0] - (hut[v] == 0), C[1] - (hut[v] == 1)});
		K = val(0);
		ans += min(K[0], K[1]);
		return ans;
	}
	if(hut[v] != hut[O])
		--ans;
	ans += C[(hut[O] ^ 1)];
	add(par[v], O, array<int, 2>{C[0] - (hut[v] == 0), C[1] - (hut[v] == 1)});
	return ans;
}/*

int readInt(){
	int i;
	if(scanf("%d",&i)!=1){
		fprintf(stderr,"Error while reading input\n");
		exit(1);
	}
	return i;
}

int main(){
	int N=readInt();
	
	std::vector<int> A(N-1),B(N-1);
	for(int i=0;i<N-1;i++)
	{
		A[i]=readInt();
		B[i]=readInt();
	}
	int Q;
	assert(scanf("%d",&Q)==1);
	std::vector <int> T(Q),V(Q);
	for(int i=0;i<Q;i++)
	{
		T[i]=readInt();
		V[i]=readInt();
	}
	
	initialize(N,A,B);
	
	std::vector<int> res(Q);
	for(int j=0;j<Q;j++)
	{
		if(T[j]==1) res[j]=cat(V[j]);
		else if(T[j]==2) res[j]=dog(V[j]);
		else res[j]=neighbor(V[j]);
	}
	for(int j=0;j<Q;j++)
		printf("%d\n",res[j]);
	return 0;
}*/

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