제출 #1315080

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1315080		jahongir	Cats or Dogs (JOI18_catdog)	C++20	100 / 100	209 ms	27620 KiB

catdog

#include "catdog.h"
#include <bits/stdc++.h>
using namespace std;

typedef pair<int,int> pii;

template<typename T> struct AINT{
	vector<T> aint; int n;
	void init(int _n){n=_n;aint.assign(2*n+5,T());}
	template<class CB> void walk(CB&& cb){walk(cb,1,n);}
	template<class CB> void walk(CB&& cb, int l, int r){walk(cb,l,r,1,1,n);}
	template<class CB> void walk(CB&& cb, int l, int r, int node, int cl, int cr){
		if(cr < l || r < cl) return;
		if(l <= cl && cr <= r && !cb(aint[node],cl,cr)) return;
		int mid = (cl+cr)>>1, L = node+1, R = node + (mid-cl+1)*2;
		walk(cb,l,r,L,cl,mid); walk(cb,l,r,R,mid+1,cr);
		aint[node].pull(aint[L],aint[R]);
	}
};

struct Node{
	array<array<int,2>,2> dp;
	Node(){dp[0][0]=dp[0][1]=dp[1][0]=dp[1][1]=0;}
	int& operator()(int i, int j){return dp[i][j];}

	void pull(Node a, Node b){
        dp[0][0] = min({a(0,0)+b(0,0),a(0,1)+b(1,0),a(0,0)+b(1,0)+1,a(0,1)+b(0,0)+1});
        dp[0][1] = min({a(0,0)+b(0,1),a(0,1)+b(1,1),a(0,0)+b(1,1)+1,a(0,1)+b(0,1)+1});
        dp[1][0] = min({a(1,0)+b(0,0),a(1,1)+b(1,0),a(1,0)+b(1,0)+1,a(1,1)+b(0,0)+1});
        dp[1][1] = min({a(1,0)+b(0,1),a(1,1)+b(1,1),a(1,0)+b(1,1)+1,a(1,1)+b(0,1)+1});
    }
}id;

Node operator+(Node a,Node b){
	Node res; res.pull(a,b);
	return res;
}

const int mxn = 1e5+1, inf = 1e8;
vector<int> g[mxn];
int par[mxn],head[mxn],tin[mxn],tout[mxn];
int heavy[mxn],cur_pos=0;

AINT<Node> segtree[mxn];
char col[mxn];
int dp[mxn][2];

void upd_node(int u){
	segtree[head[u]].walk([&](Node &val, int l, int r){
		val(0,0) = dp[u][0];
		val(1,1) = dp[u][1];
		if(col[u]!=-1)
			val(1-col[u],1-col[u]) = inf;
		return 0;
	},tin[u],tin[u]);

}

int pre_dfs(int u = 1, int p = 0){
	int sz = 1, mx = 0; par[u]=p;
	for(auto v : g[u]) if(v!=p){
		int vsz = pre_dfs(v,u);
		sz += vsz;
		if(mx < vsz)
			heavy[u] = v, mx = vsz;
	}
	return sz;
}

void decompose(int u=1, int h=1){
	if(u==h) tin[u] = 1;
	else tin[u] = tin[par[u]]+1;
	head[u] = h, tout[h]=tin[u];
	if(heavy[u]) decompose(heavy[u],h);
	dp[u][0] = dp[u][1] = 0;
	for(auto v : g[u]) if(v!=par[u]&&v!=heavy[u])
		decompose(v,v);
	
	if(u==h) segtree[u].init(tout[u]-tin[u]+1);
}

void decompose2(int u=1, int h=1){
	if(heavy[u]) decompose2(heavy[u]);
	for(auto v : g[u]) if(v!=par[u]&&v!=heavy[u])
		decompose2(v,v);
	segtree[head[u]].walk([&](Node &val, int l, int r){
		val(0,0) = val(1,1) = 0;
		val(0,1) = val(1,0) = inf;
		return 0;
	},tin[u],tin[u]);
}

int update(int v, int x){
	int u = head[v];
	vector<int> vec;
	for(; u!=1; u=head[par[u]]){
		vec.emplace_back(u);
	}
	for(; !vec.empty(); vec.pop_back()){
		u = vec.back();
		auto val = segtree[u].aint[1];
		int a = min(val(0,0),val(0,1));
		int b = min(val(1,0),val(1,1));
		dp[par[u]][0] -= min(a,b+1);
		dp[par[u]][1] -= min(a+1,b);
		upd_node(par[u]);
	}

	col[v] = x; upd_node(v);
	u = head[v];
	for(; u!=1; u=head[par[u]]){
		auto val = segtree[u].aint[1];
		int a = min(val(0,0),val(0,1));
		int b = min(val(1,0),val(1,1));
		dp[par[u]][0] += min(a,b+1);
		dp[par[u]][1] += min(a+1,b);
		upd_node(par[u]);
	}

	auto val = segtree[1].aint[1];
	return min({val(0,0),val(0,1),val(1,0),val(1,1)});
}

void initialize(int N, std::vector<int> A, std::vector<int> B) {
	for(int i = 0; i < N-1; i++){
		g[A[i]].emplace_back(B[i]);
		g[B[i]].emplace_back(A[i]);
	}
	pre_dfs(); decompose();
	decompose2();
	fill(col+1,col+N+1,-1);
}


int cat(int v) {
	return update(v,0);
}

int dog(int v) {
	return update(v,1);
}

int neighbor(int v) {
	return update(v,-1);
}

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