Submission #921010

#	Time	Username	Problem	Language	Result	Execution time	Memory
921010		KiaRez	Cats or Dogs (JOI18_catdog)	C++17	100 / 100	732 ms	44404 KiB

catdog

/*
    IN THE NAME OF GOD
*/
#include <bits/stdc++.h>

// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef long double ld;

#define F                                      first
#define S                                      second
#define Mp                                     make_pair
#define pb                                     push_back
#define pf                                     push_front
#define size(x)                                ((ll)x.size())
#define all(x)                                 (x).begin(),(x).end()
#define kill(x)		                           cout << x << '\n', exit(0);
#define fuck(x)                                cout << "(" << #x << " , " << x << ")" << endl
#define endl                                   '\n'

const int N = 3e5+23, lg = 17;
ll Mod = 998244353;

inline ll MOD(ll a, ll mod=Mod) {a%=mod; (a<0)&&(a+=mod); return a;}
inline ll poww(ll a, ll b, ll mod=Mod) {
    ll ans = 1;
    a=MOD(a, mod);
    while (b) {
        if (b & 1) ans = MOD(ans*a, mod);
        b >>= 1;
        a = MOD(a*a, mod);
    }
    return ans;
}

struct node {
	int dp[2][2];
	node() {dp[0][0]=dp[0][1]=dp[1][0]=dp[1][1]=0; dp[0][1]=dp[1][0]=N;}
} seg[N];

node merge(node x, node y) {
	node z;
	for(int i=0; i<2; i++) {
	for(int j=0; j<2; j++) { 
z.dp[i][j] = min({x.dp[i][1]+y.dp[1][j], x.dp[i][0]+y.dp[0][j], x.dp[i][0]+y.dp[1][j]+1, 1+x.dp[i][1]+y.dp[0][j]});
	}
	}
	return z;
}

int n, tim, dwn[N], tin[N], tout[N], par[N], head[N], h[N], subt[N], typ[N];
int ttmp[2][2][N];
vector<int> adj[N];

void init(int v, int p=0) {
	par[v]=p, h[v]=h[p]+1, subt[v]=1;
	for(int u : adj[v]) {
		if(u == p) continue;
		init(u, v); subt[v] += subt[u];
	}
}

void dfs(int v, int p) {
	int mx = 0;
	tin[v] = ++tim, head[v] = p, dwn[p] = v;
	for(int u : adj[v]) if(u!=par[v]) mx = (subt[mx] > subt[u] ? mx : u);
	if(mx > 0) dfs(mx, p);
	for(int u : adj[v]) if(u!=par[v] && u!=mx) dfs(u, u);
	tout[v] = tim+1;
}

void update(int ind, node val) {
	if(ind == 0) return;
	if(ind >= (1<<lg)) {
		seg[ind] = val;
	} else {
		seg[ind] = merge(seg[2*ind], seg[2*ind+1]);
	}
	update(ind/2, val);
}

node query(int l, int r, int ind=1, int lc=1, int rc=(1<<lg)+1) {
	if(lc>=l && rc<=r) return seg[ind];
	int mid = (lc+rc)/2;
	if(r<=mid) return query(l, r, 2*ind, lc, mid);
	if(l>=mid) return query(l, r, 2*ind+1, mid, rc);
	return merge(query(l, r, 2*ind, lc, mid), query(l, r, 2*ind+1, mid, rc));
}

void initialize(int _n, vector<int> A, vector<int> B) {
	n=_n;
	for(int i=0; i<n-1; i++) adj[A[i]].pb(B[i]), adj[B[i]].pb(A[i]);
	init(1);
	dfs(1, 1);
}

int ftmp[2][2][N];
void reinit(int v) {
	int u = v;
	node ct;
	while(head[v] != 1) {
		ct = query(tin[head[v]], tin[dwn[head[v]]]+1);
		node tmp = query(tin[par[head[v]]], tin[par[head[v]]]+1);
		v=par[head[v]];
		ftmp[0][0][tin[v]] += min({ct.dp[1][0]+1, ct.dp[1][1]+1, ct.dp[0][1], ct.dp[0][0]});
		ftmp[1][0][tin[v]] += min({ct.dp[1][0]+1, ct.dp[1][1]+1, ct.dp[0][1], ct.dp[0][0]});
		ftmp[0][1][tin[v]] += min({ct.dp[0][1]+1, ct.dp[0][0]+1, ct.dp[1][0], ct.dp[1][1]});
		ftmp[1][1][tin[v]] += min({ct.dp[0][1]+1, ct.dp[0][0]+1, ct.dp[1][0], ct.dp[1][1]});
		update(tin[v]+(1<<lg)-1, tmp);
	}

	v = u;
	while(head[v] != 1) {
		ct = query(tin[head[v]], tin[dwn[head[v]]]+1);
		node tmp = query(tin[par[head[v]]], tin[par[head[v]]]+1);
		v=par[head[v]];
		tmp.dp[0][0] -= ftmp[0][0][tin[v]];
		tmp.dp[1][0] -= ftmp[1][0][tin[v]];
		tmp.dp[0][1] -= ftmp[0][1][tin[v]];
		tmp.dp[1][1] -= ftmp[1][1][tin[v]];
		ttmp[0][0][tin[v]] -= ftmp[0][0][tin[v]];
		ttmp[1][0][tin[v]] -= ftmp[1][0][tin[v]];
		ttmp[0][1][tin[v]] -= ftmp[0][1][tin[v]];
		ttmp[1][1][tin[v]] -= ftmp[1][1][tin[v]];
		update(tin[v]+(1<<lg)-1, tmp);
		for(int i=0; i<2; i++) for(int j=0; j<2; j++) ftmp[i][j][tin[v]] = 0;
	}
}

int cat(int v) {
	reinit(v);
	typ[v] = 1;
	
	node ct;
	ct.dp[1][0]=ct.dp[1][1]=ct.dp[0][1]=n;
	if(v==1) ct.dp[1][0] = 0;
	for(int i=0; i<2; i++) for(int j=0; j<2; j++) ct.dp[i][j] += ttmp[i][j][tin[v]];
	update(tin[v]+(1<<lg)-1, ct);
	while(head[v] != 1) {
		ct = query(tin[head[v]], tin[dwn[head[v]]]+1);
		node tmp = query(tin[par[head[v]]], tin[par[head[v]]]+1);
		tmp.dp[0][0] += min({ct.dp[1][0]+1, ct.dp[1][1]+1, ct.dp[0][1], ct.dp[0][0]});
		tmp.dp[1][0] += min({ct.dp[1][0]+1, ct.dp[1][1]+1, ct.dp[0][1], ct.dp[0][0]});
		tmp.dp[0][1] += min({ct.dp[0][1]+1, ct.dp[0][0]+1, ct.dp[1][0], ct.dp[1][1]});
		tmp.dp[1][1] += min({ct.dp[0][1]+1, ct.dp[0][0]+1, ct.dp[1][0], ct.dp[1][1]});
		v=par[head[v]];
		ttmp[0][0][tin[v]] += min({ct.dp[1][0]+1, ct.dp[1][1]+1, ct.dp[0][1], ct.dp[0][0]});
		ttmp[1][0][tin[v]] += min({ct.dp[1][0]+1, ct.dp[1][1]+1, ct.dp[0][1], ct.dp[0][0]});
		ttmp[0][1][tin[v]] += min({ct.dp[0][1]+1, ct.dp[0][0]+1, ct.dp[1][0], ct.dp[1][1]});
		ttmp[1][1][tin[v]] += min({ct.dp[0][1]+1, ct.dp[0][0]+1, ct.dp[1][0], ct.dp[1][1]});
		update(tin[v]+(1<<lg)-1, tmp);
	}

	ct = query(tin[1], tin[dwn[1]]+1);
	return min({ct.dp[0][0], ct.dp[0][1], ct.dp[1][1], ct.dp[1][0]});
}

int dog(int v) {
	reinit(v);
	typ[v] = 2;

	node ct;
	ct.dp[1][0]=ct.dp[0][0]=ct.dp[0][1]=n;
	if(v==1) ct.dp[0][1] = 0;
	for(int i=0; i<2; i++) for(int j=0; j<2; j++) ct.dp[i][j] += ttmp[i][j][tin[v]];
	update(tin[v]+(1<<lg)-1, ct);
	while(head[v] != 1) {
		ct = query(tin[head[v]], tin[dwn[head[v]]]+1);
		node tmp = query(tin[par[head[v]]], tin[par[head[v]]]+1);
		tmp.dp[0][0] += min({ct.dp[1][0]+1, ct.dp[1][1]+1, ct.dp[0][1], ct.dp[0][0]});
		tmp.dp[1][0] += min({ct.dp[1][0]+1, ct.dp[1][1]+1, ct.dp[0][1], ct.dp[0][0]});
		tmp.dp[0][1] += min({ct.dp[0][1]+1, ct.dp[0][0]+1, ct.dp[1][0], ct.dp[1][1]});
		tmp.dp[1][1] += min({ct.dp[0][1]+1, ct.dp[0][0]+1, ct.dp[1][0], ct.dp[1][1]});
		v=par[head[v]];
		ttmp[0][0][tin[v]] += min({ct.dp[1][0]+1, ct.dp[1][1]+1, ct.dp[0][1], ct.dp[0][0]});
		ttmp[1][0][tin[v]] += min({ct.dp[1][0]+1, ct.dp[1][1]+1, ct.dp[0][1], ct.dp[0][0]});
		ttmp[0][1][tin[v]] += min({ct.dp[0][1]+1, ct.dp[0][0]+1, ct.dp[1][0], ct.dp[1][1]});
		ttmp[1][1][tin[v]] += min({ct.dp[0][1]+1, ct.dp[0][0]+1, ct.dp[1][0], ct.dp[1][1]});
		update(tin[v]+(1<<lg)-1, tmp);
	}

	ct = query(tin[1], tin[dwn[1]]+1);
	return min({ct.dp[0][0], ct.dp[0][1], ct.dp[1][1], ct.dp[1][0]});
}

int neighbor(int v) {
	reinit(v);
	typ[v] = 0;

	node ct;
	for(int i=0; i<2; i++) for(int j=0; j<2; j++) ct.dp[i][j] += ttmp[i][j][tin[v]];
	update(tin[v]+(1<<lg)-1, ct);
	while(head[v] != 1) {
		ct = query(tin[head[v]], tin[dwn[head[v]]]+1);
		node tmp = query(tin[par[head[v]]], tin[par[head[v]]]+1);
		tmp.dp[0][0] += min({ct.dp[1][0]+1, ct.dp[1][1]+1, ct.dp[0][1], ct.dp[0][0]});
		tmp.dp[1][0] += min({ct.dp[1][0]+1, ct.dp[1][1]+1, ct.dp[0][1], ct.dp[0][0]});
		tmp.dp[0][1] += min({ct.dp[0][1]+1, ct.dp[0][0]+1, ct.dp[1][0], ct.dp[1][1]});
		tmp.dp[1][1] += min({ct.dp[0][1]+1, ct.dp[0][0]+1, ct.dp[1][0], ct.dp[1][1]});
		v=par[head[v]];
		ttmp[0][0][tin[v]] += min({ct.dp[1][0]+1, ct.dp[1][1]+1, ct.dp[0][1], ct.dp[0][0]});
		ttmp[1][0][tin[v]] += min({ct.dp[1][0]+1, ct.dp[1][1]+1, ct.dp[0][1], ct.dp[0][0]});
		ttmp[0][1][tin[v]] += min({ct.dp[0][1]+1, ct.dp[0][0]+1, ct.dp[1][0], ct.dp[1][1]});
		ttmp[1][1][tin[v]] += min({ct.dp[0][1]+1, ct.dp[0][0]+1, ct.dp[1][0], ct.dp[1][1]});
		update(tin[v]+(1<<lg)-1, tmp);
	}

	ct = query(tin[1], tin[dwn[1]]+1);
	return min({ct.dp[0][0], ct.dp[0][1], ct.dp[1][1], ct.dp[1][0]});
}

/*
int main () {

	initialize(7, {1, 2, 3, 1, 5, 1}, {2, 3, 4, 5, 6, 7});
	
	cout<< cat(1)<<endl;
	cout<< dog(5)<<endl;
	cout<< dog(4)<<endl;
	cout<< dog(2)<<endl;
	cout<< dog(7)<<endl;
	cout<< dog(3)<<endl;
	cout<< dog(6)<<endl;
	cout<< neighbor(1)<<endl;
	
	// tmp2 = merge(tmp2, tmp1);
	// fuck(tmp2.dp[0][0]);
	// fuck(tmp2.dp[1][0]);
	// fuck(tmp2.dp[0][1]);
	// fuck(tmp2.dp[1][1]);

	return 0;
}
*/

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