제출 #1151375

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1151375		AgentPengin	Cats or Dogs (JOI18_catdog)	C++20	0 / 100	3 ms	6468 KiB

catdog

/**
 *    author:  AgentPengin ( Độc cô cầu bại )
 *    created: 23.12.2022 10:08:02
 *    too lazy to update time
**/
#include "catdog.h"
#include<bits/stdc++.h>

#define EL '\n'
#define fi first
#define se second
#define NAME "TASK"
#define ll long long
#define lcm(a,b) (a/gcd(a,b))*b
#define db(val) "["#val" = " << (val) << "] "
#define bend(v) (v).begin(),(v).end()
#define sz(v) (int)(v).size()
#define ex exit(0)

using namespace std;

const ll mod = 1e9 + 7;
const int inf = 1e9;
const int MAXN = 1e5 + 5;
const int N = MAXN;

int n, sz[MAXN], c[MAXN];
vector<int> adj[MAXN];
int par[MAXN];

struct Node {
	int dp[2][2];
	Node (int a = 0, int b = 0, int c = 0, int d = 0) {
		dp[0][0] = a;
		dp[0][1] = b;
		dp[1][0] = c;
		dp[1][1] = d;
	}
};

Node operator + (const Node& x, const Node& y) {
	Node res = Node(inf, inf, inf, inf);
	for (int i = 0;i < 2;i++) {
		for (int j = 0;j < 2;j++) {
			for (int k = 0;k < 2;k++) {
				for (int l = 0;l < 2;l++) {
					res.dp[i][l] = min(res.dp[i][l], x.dp[i][j] + y.dp[k][l] + (j ^ k));
				}
			}
		}
	}
	return res;
}

struct Segtree {
	vector<Node> st;
	int n;
	void build(int id, int l,int r) {
		if (l == r) {
			st[id] = Node(0, inf, inf, 0);
			return;
		}
		int mid = l + r >> 1;
		build(id << 1, l, mid);
		build(id << 1 | 1, mid + 1, r);
		st[id] = st[id << 1] + st[id << 1 | 1];
	}
	void upd(int id, int l, int r, int pos, int val1, int val2) {
		if (l == r) {
			st[id].dp[0][0] += val1;
			st[id].dp[1][1] += val2;
			return;
		}
		int mid = l + r >> 1;
		if (pos <= mid) {
			upd(id << 1, l, mid, pos, val1, val2);
		} else {
			upd(id << 1 | 1,mid + 1, r, pos, val1, val2);
		}
		st[id] = st[id << 1] + st[id << 1 | 1];
	}
	void init(int sz) {
		n = sz;
		st.resize(n * 4);
		build(1, 1, n);
	}
	pair<int,int> get() {
		pair<int,int> res;
		res.fi = min(st[1].dp[0][0], st[1].dp[0][1]);
		res.se = min(st[1].dp[1][0], st[1].dp[1][1]);
		return make_pair(min(res.fi, res.se + 1), min(res.fi + 1, res.se));
	}
} seg[MAXN];

void dfs1(int u, int p) {
	par[u] = p;
	sz[u] = 1;
	for (auto v : adj[u]) {
		if (v != p) {
			dfs1(v, u);
			sz[u] += sz[v];
		}
	}
	for (auto &v : adj[u]) {
		if (v == p) {
			swap(adj[u][sz(adj[u]) - 1],v);
			adj[u].pop_back();
			break;
		}
	}
	sort(bend(adj[u]), [&](int x,int y){
		return sz[x] > sz[y];
	});
}

int tin = 0, head[MAXN], pos[MAXN];

void dfs2(int u, int p, int cur) {
	par[u] = cur;
	if (sz[cur] == 0) {
		head[cur] = p;
	}
	pos[u] = ++sz[cur];
	for (auto v : adj[u]) {
		if (adj[u].front() == v) {
			dfs2(v, u, cur);
		} else {
			dfs2(v, u, tin++);
		}
	}
}

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]);
	}
	dfs1(1, 0);
	memset(par, 0, sizeof par);
	memset(sz, 0, sizeof sz);
	dfs2(1, 0, tin++);
	for (int i = 0;i < tin;i++) {
		seg[i].init(sz[i]);
	}
}

int upd(int u, int val1, int val2) {
	while(u != 0) {
		int cur = par[u];
		auto [a0, a1] = seg[cur].get();
		seg[cur].upd(1, 1, sz[cur], pos[u], val1, val2);
		auto [b0, b1] = seg[cur].get();
		val1 = b0 - a0;
		val2 = b1 - a1;
		u = head[u];
	}
	auto [a, b] = seg[0].get();
	return min(a, b);
}

int cat(int u) {
	c[u] = 1;
	int res = upd(u, N, 0);
	return res;
}

int dog(int u) {
	c[u] = 2;
	int res = upd(u, 0, N);
	return res;
}

int neighbor(int u) {
	int res = 0;
	if (c[u] == 1) {
		res = upd(u, -N, 0);
	} else {
		res = upd(u, 0, -N);
	}
	c[u] = 0;
	return res;
}

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