Submission #1278324

#	Time	Username	Problem	Language	Result	Execution time	Memory
1278324		arashmemar	Synchronization (JOI13_synchronization)	C++20	100 / 100	154 ms	20288 KiB

synchronization

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

const int maxn = 1e5 + 100, inf = 1e9;

pair <int, int> ans[maxn];

int st[maxn], ft[maxn], h[maxn], t = 1;

pair <int, int> m[4 * maxn];

bool mark[maxn], isp[maxn], isa[maxn];

vector <int> ne[maxn], s;

vector <pair <int, int> > es;

void dfs(int v)
{
	mark[v] = 1;
	st[v] = t;
	t++;
	s.push_back(v);
	for (int i = 0;i < ne[v].size();i++)
	{
		int u = ne[v][i];
		if (mark[u])
		{
			continue;
		}
		h[u] = h[v] + 1;
		dfs(u);
	}
	ft[v] = t;
	return ;
}

void update(int id, int L, int R, int p, int v)
{
	if (R - L == 1)
	{
		m[id].first = v * ft[s[L]];
		m[id].second = s[L];

		return ;
	}
	int mid = (L + R) / 2;
	if (p < mid)
	{
		update(id * 2 + 0, L, mid, p, v);
	}
	else
	{
		update(id * 2 + 1, mid, R, p, v);
	}
	m[id] = max(m[id * 2 + 0], m[id * 2 + 1]);
	return;
}

pair<int, int> get(int id, int L, int R, int l, int r, int v)
{
	if (m[id] < make_pair(v, inf))
	{
		return {0, 0};
	}
	if (R - L == 1)
	{
		return m[id];
	}
	int mid = (L + R) / 2;
	pair <int, int> ret = {0, 0};	
	if (r > mid)
	{
		ret = max(ret, get(id * 2 + 1, mid, R, max(l, mid), r, v));
	}

	if (ret != make_pair(0, 0))
	{
		return ret;
	}

	if (l < mid)
	{
		ret = max(ret, get(id * 2 + 0, L, mid, l, min(r, mid), v));
	}

	return ret;
}

int main()
{

	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	s.push_back(0);
	es.push_back({0, 0});
	int n, m, q;
	cin >> n >> m >> q;
	for (int i = 1;i < n;i++)
	{
		int v, u;
		cin >> v >> u;
		ne[v].push_back(u);
		ne[u].push_back(v);
		es.push_back({v, u});
	}

	dfs(1);

	for (int i = 1;i <= n;i++)
	{
		update(1, 1, n + 1, i, 1);
		isp[i] = 1;
		ans[i].first = 1;
	}

	for (int i = 0;i < m;i++)
	{
		int e;
		cin >> e;
		int v = es[e].first, u = es[e].second;
		if (h[v] < h[u])
		{
			swap(v, u);
		}
		int op = get(1, 1, n + 1, 1, st[u] + 1, st[u]).second;
		isa[e] ^= 1;
		if (isa[e])
		{
			isp[v] = 0;
			ans[op].first += ans[v].first - ans[v].second;
		}
		else
		{
			isp[v] = 1;
			ans[v].first = ans[v].second = ans[op].first;
		}
		update(1, 1, n + 1, st[v], isp[v]);

//		print(n);
//		cout << endl;

	}

	while (q--)
	{
		int v;
		cin >> v;
		int par = get(1, 1, n + 1, 1, st[v] + 1, st[v]).second;
		cout << ans[par].first << '\n';
	}

}

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