제출 #600485

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
600485		GusterGoose27	동기화 (JOI13_synchronization)	C++11	100 / 100	501 ms	61360 KiB

synchronization

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;

class upd {
public:
	int a, b;
	int id;
	upd(int an, int bn, int i) {
		a = an;
		b = bn;
		id = i;
	}
	upd() {}
};

const int MAXN = 1e5;
const int MAXM = 2e5;
bitset<MAXN> bsets[MAXN];
int last_sync[MAXN]; // edges
int info[MAXN];
int uf[MAXN];
int ufrank[MAXN];
vector<int> par_set;
vector<int> ufrank_set;
int n, m, q;
upd edges[MAXN];

int find(int i) {
	return (uf[i] == -1) ? i : find(uf[i]);
}

void merge(upd &u) {
	int r1 = find(u.a);
	int r2 = find(u.b);
	if (ufrank[r1] > ufrank[r2]) {
		int temp = r1; r1 = r2; r2 = temp;
	}
	par_set.push_back(r1);
	uf[r1] = r2;
	info[r2] += info[r1]-last_sync[u.id];
	if (ufrank[r1] == ufrank[r2]) {
		ufrank[r2]++;
		ufrank_set.push_back(r2);
	}
	else ufrank_set.push_back(-1);
}

class stree {
public:
	int lt, rt;
	stree *l = nullptr;
	stree *r = nullptr;
	vector<upd> merges;
	stree(int lp, int rp) {
		lt = lp;
		rt = rp;
		if (rp > lp) {
			int m = (lt+rt)/2;
			l = new stree(lt, m);
			r = new stree(m+1, rt);
		}
	}
	void update(upd &m, int lm, int rm) {
		if (lt > rm || rt < lm) return;
		if (lt >= lm && rt <= rm) {
			merges.push_back(m);
			return;
		}
		l->update(m, lm, rm);
		r->update(m, lm, rm);
	}
	void dfs() {
		for (upd u: merges) merge(u);
		if (l) l->dfs();
		if (r) r->dfs();
		for (int i = merges.size()-1; i >= 0; i--) {
			int p = par_set.back();
			par_set.pop_back();
			int r = ufrank_set.back();
			ufrank_set.pop_back();
			info[p] = info[uf[p]];
			last_sync[merges[i].id] = info[p];
			uf[p] = -1;
			if (r >= 0) ufrank[r]--;
		}
	}
};

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> n >> m >> q;
	for (int i = 0; i < n-1; i++) {
		int x, y; cin >> x >> y; x--; y--;
		edges[i] = upd(x, y, i);
	}
	map<int, int> prev;
	stree *tree = new stree(0, m-1);
	fill(uf, uf+n, -1);
	fill(info, info+n, 1);
	for (int i = 0; i < m; i++) {
		int x; cin >> x; x--;
		if (prev.find(x) == prev.end()) prev[x] = i;
		else {
			tree->update(edges[x], prev[x], i);
			prev.erase(x);
		}
	}
	for (auto val: prev) {
		tree->update(edges[val.first], val.second, m-1);
	}
	tree->dfs();
	for (int i = 0; i < q; i++) {
		int x; cin >> x; x--;
		cout << info[find(x)] << "\n";
	}
}

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