제출 #156451

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
156451		Saboon	동기화 (JOI13_synchronization)	C++14	0 / 100	3 ms	632 KiB

synchronization

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int mod = 1e9 + 7;
const int maxn = 5;

int n;
int parent[maxn], h[maxn], sz[maxn], pos[maxn], st[maxn], ft[maxn], up[maxn];
vector<int> t[maxn];
bitset<maxn> bs[maxn];
int Time = 0;
int seg[4 * maxn];
pair<int,int> edge[2 * maxn];
bool black[maxn];

int get(int id, int L, int R, int l, int r){
	if (r <= L or R <= l or seg[id] == 1)
		return -1;
	if (L + 1 == R)
		return L;
	int mid = (L + R) >> 1;
	return max(get(2 * id + 0, L, mid, l, r), get(2 * id + 1, mid, R, l, r));
}

void add(int id, int L, int R, int idx, bool val){
	if (idx < L or R <= idx)
		return;
	if (L + 1 == R){
		seg[id] = val;
		return;
	}
	int mid = (L + R) >> 1;
	add(2 * id + 0, L, mid, idx, val);
	add(2 * id + 1, mid, R, idx, val);
	seg[id] = min(seg[2 * id + 0], seg[2 * id + 1]);
}

int get_par(int v){
	while (v != 0){
		int me = get(1, 0, n, st[up[v]], st[v] + 1);
		if (me != -1)
			return pos[me];
		v = parent[up[v]];
	}
	return v;
}

void add(int v, int par){
	int u = get_par(par);
	bs[u] |= bs[v];
	add(1, 0, n, st[v], 1);
}

void del(int v, int par){
	int u = get_par(par);
	bs[v] = bs[u];
	add(1, 0, n, st[v], 0);
}

bool cmpsz(int v, int u){ return sz[v] < sz[u]; }
void dfs(int v, int par = -1){
	st[v] = Time;
	pos[Time ++] = v;
	sort(t[v].begin(), t[v].end(), cmpsz);
	if (par != -1) //t[v].back() = par
		t[v].pop_back();
	reverse(t[v].begin(), t[v].end());
	bool heavy = true;
	for (auto u : t[v]){
		if (heavy == true)
			up[u] = up[v];
		else
			up[u] = u;
		dfs(u, v);
		heavy = false;
	}
	ft[v] = Time;
}

void dfs_sz(int v, int par = -1){
	parent[v] = par;
	sz[v] = 1;
	for (auto u : t[v])
		if (u != par)
			h[u] = h[v] + 1, dfs_sz(u, v), sz[v] += sz[u];
}

int main(){
	ios_base::sync_with_stdio (false);
	int m, q;
	cin >> n >> m >> q;
	for (int i = 0; i < n - 1; i++){
		int v, u;
		cin >> v >> u;
		v --, u --;
		t[v].push_back(u);
		t[u].push_back(v);
		edge[i] = {v, u};
	}
	dfs_sz(0);
	dfs(0);
	for (int i = 0; i < n; i++)
		bs[i][i] = 1;
	for (int i = 0; i < m; i++){
		int idx;
		cin >> idx;
		idx --;
		int v = edge[idx].first, u = edge[idx].second;
		if (h[v] < h[u])
			swap(v, u);
		if (black[v])
			del(v, u);
		else
			add(v, u);
		black[v] ^= 1;
	}
	for (int i = 0; i < q; i++){
		int v;
		cin >> v;
		v --;
		v = get_par(v);
		cout << bs[v].count() << '\n';
	}
}

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