제출 #934325

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
934325		vjudge1	동기화 (JOI13_synchronization)	C++17	0 / 100	289 ms	23244 KiB

synchronization

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

const int MAX = 2e5 + 5;

struct Data {
	int sum, mn, mx, sz;

	Data() : sum(0), mn(INT_MAX), mx(INT_MIN), sz(0) {}

	Data(int val) : sum(val), mn(val), mx(val), sz(1) {}

	Data(int _sum, int _mn, int _mx, int _sz) : sum(_sum), mn(_mn), mx(_mx), sz(_sz) {}
};

struct Lazy {
	int a, b;

	Lazy(int _a = 1, int _b = 0) : a(_a), b(_b) {}

	bool lazy() {
		return a != 1 || b != 0;
	}
};

Data operator + (const Data &a, const Data &b) {
	return Data(a.sum + b.sum, min(a.mn, b.mn), max(a.mx, b.mx), a.sz + b.sz);
}

Data& operator += (Data &a, const Data &b) {
	return a = a + b;
}

Lazy& operator += (Lazy &a, const Lazy &b) {
	return a = Lazy(a.a * b.a, a.b * b.a + b.b);
}

int& operator += (int &a, const Lazy &b) {
	return a = a * b.a + b.b;
}

Data& operator += (Data &a, const Lazy &b) {
	return a.sz ? a = Data(a.sum * b.a + a.sz * b.b, a.mn * b.a + b.b, a.mx * b.a + b.b, a.sz) : a;
}

struct Node {
	int p, ch[4], val;
	Data path, sub, all;
	Lazy plazy, slazy;
	bool flip, fake;

	Node() : p(0), ch(), path(), sub(), all(), plazy(), slazy(), flip(false), fake(true) {}

	Node(int _val) : Node() {
		val = _val;
		path = all = Data(val);
		fake = false;
	}
} tr[MAX];
vector<int> freeList;

void pushFlip(int u) {
	if (!u)
		return;
	swap(tr[u].ch[0], tr[u].ch[1]);
	tr[u].flip ^= true;
}

void pushPath(int u, const Lazy &lazy) {
	if (!u || tr[u].fake)
		return;
	tr[u].val += lazy;
	tr[u].path += lazy;
	tr[u].all = tr[u].path + tr[u].sub;
	tr[u].plazy += lazy;
}

void pushSub(int u, bool o, const Lazy &lazy) {
	if (!u)
		return;
	tr[u].sub += lazy;
	tr[u].slazy += lazy;
	if (!tr[u].fake && o)
		pushPath(u, lazy);
	else
		tr[u].all = tr[u].path + tr[u].sub;
}

void push(int u) {
	if (!u)
		return;
	if (tr[u].flip) {
		pushFlip(tr[u].ch[0]);
		pushFlip(tr[u].ch[1]);
		tr[u].flip = false;
	}
	if (tr[u].plazy.lazy()) {
		pushPath(tr[u].ch[0], tr[u].plazy);
		pushPath(tr[u].ch[1], tr[u].plazy);
		tr[u].plazy = Lazy();
	}
	if (tr[u].slazy.lazy()) {
		pushSub(tr[u].ch[0], false, tr[u].slazy);
		pushSub(tr[u].ch[1], false, tr[u].slazy);
		pushSub(tr[u].ch[2], true, tr[u].slazy);
		pushSub(tr[u].ch[3], true, tr[u].slazy);
		tr[u].slazy = Lazy();
	}
}

void pull(int u) {
	if (!tr[u].fake)
		tr[u].path = tr[tr[u].ch[0]].path + tr[tr[u].ch[1]].path + tr[u].val;
	tr[u].sub = tr[tr[u].ch[0]].sub + tr[tr[u].ch[1]].sub + tr[tr[u].ch[2]].all + tr[tr[u].ch[3]].all;
	tr[u].all = tr[u].path + tr[u].sub;
}

void attach(int u, int d, int v) {
	tr[u].ch[d] = v;
	tr[v].p = u;
	pull(u);
}

int dir(int u, int o) {
	int v = tr[u].p;
	return tr[v].ch[o] == u ? o : tr[v].ch[o + 1] == u ? o + 1 : -1;
}

void rotate(int u, int o) {
	int v = tr[u].p, w = tr[v].p, du = dir(u, o), dv = dir(v, o);
	if (dv == -1 && o == 0)
		dv = dir(v, 2);
	attach(v, du, tr[u].ch[du ^ 1]);
	attach(u, du ^ 1, v);
	if (~dv)
		attach(w, dv, u);
	else
		tr[u].p = w;
}

void splay(int u, int o) {
	push(u);
	while (~dir(u, o) && (o == 0 || tr[tr[u].p].fake)) {
		int v = tr[u].p, w = tr[v].p;
		push(w);
		push(v);
		push(u);
		int du = dir(u, o), dv = dir(v, o);
		if (~dv && (o == 0 || tr[w].fake))
			rotate(du == dv ? v : u, o);
		rotate(u, o);
	}
}

void add(int u, int v) {
	if (!v)
		return;
	for (int i = 2; i < 4; i++)
		if (!tr[u].ch[i]) {
			attach(u, i, v);
			return;
		}
	int w = freeList.back();
	freeList.pop_back();
	attach(w, 2, tr[u].ch[2]);
	attach(w, 3, v);
	attach(u, 2, w);
}

void recPush(int u) {
	if (tr[u].fake)
		recPush(tr[u].p);
	push(u);
}

void rem(int u) {
	int v = tr[u].p;
	recPush(v);
	if (tr[v].fake) {
		int w = tr[v].p;
		attach(w, dir(v, 2), tr[v].ch[dir(u, 2) ^ 1]);
		if (tr[w].fake)
			splay(w, 2);
		freeList.push_back(v);
	} else {
		attach(v, dir(u, 2), 0);
	}
	tr[u].p = 0;
}

int par(int u) {
	int v = tr[u].p;
	if (!tr[v].fake)
		return v;
	splay(v, 2);
	return tr[v].p;
}

int access(int u) {
	int v = u;
	splay(u, 0);
	add(u, tr[u].ch[1]);
	attach(u, 1, 0);
	while (tr[u].p) {
		v = par(u);
		splay(v, 0);
		rem(u);
		add(v, tr[v].ch[1]);
		attach(v, 1, u);
		splay(u, 0);
	}
	return v;
}

void reroot(int u) {
	access(u);
	pushFlip(u);
}

void link(int u, int v) {
	reroot(u);
	access(v);
	add(v, u);
}

void cut(int u, int v) {
	reroot(u);
	access(v);
	tr[v].ch[0] = tr[u].p = 0;
	pull(v);
}

int lca(int u, int v) {
	access(u);
	return access(v);
}

bool same(int u, int v) {
	access(u);
	access(v);
	return tr[u].p;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int n, m, q;
	cin >> n >> m >> q;
	vector<pair<int, int>> edges;
	for (int i = 0; i < n - 1; i++) {
		int x, y;
		cin >> x >> y;
		edges.emplace_back(x, y);
	}

	for (int i = 1; i <= n; i++) {
		int w = 1;
		tr[i] = Node(w);
	}
	for (int i = n + 1; i < MAX; i++)
		freeList.push_back(i);

	auto subtree_query = [&](int u) {
		access(u);
		Data ret = tr[u].val;
		for (int i = 2; i < 4; i++)
			ret += tr[tr[u].ch[i]].all;
		return ret.mx;
	};

	auto subtree_update = [&](int u, int val) {
		access(u);
		Lazy lazy(0, val); // replace to val in all nodes in subtree of x
		tr[u].val += lazy;
		for (int i = 2; i < 4; i++)
			pushSub(tr[u].ch[i], true, lazy);
	};

	while (m--) {
		int i;
		cin >> i;
		i -= 1;
		auto [u, v] = edges[i];
		if (same(u, v)) {
			cut(u, v);
		}
		else {
			reroot(u);
			int u1 = subtree_query(u);
			reroot(v);
			int v1 = subtree_query(v);
			reroot(u);
			subtree_update(u, 0);
			reroot(v);
			subtree_update(v, 0);
			link(u, v);
			reroot(v);
			subtree_update(v, u1 + v1);
		}
	}

	while (q--) {
		int u;
		cin >> u;
		reroot(u);
		cout << subtree_query(u) << endl;
	}

	return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 20
• Subtask 3: 0 / 10
• Subtask 4: 0 / 20
• Subtask 5: 0 / 40