제출 #529014

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
529014		blue	동기화 (JOI13_synchronization)	C++17	100 / 100	247 ms	26240 KiB

synchronization

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;

const int mx = 100'000;
const int lg = 18;

using pii = pair<int, int>;
using vi = vector<int>;
using vpii = vector<pii>;

int N, M, Q;

vpii edge[1 + mx];

vi edge_node(1 + mx);
vi node_edge(1 + mx);
vi par(1 + mx, 0);

vi subtree(1 + mx, 1);
vi ord_ind(1 + mx, 0);
int ord_ct = 0;

int anc[1 + mx][1 + lg];



void dfs(int u)
{
	ord_ind[u] = ++ord_ct;

	for(auto ed : edge[u])
	{
		int v = ed.first;
		int e = ed.second;

		if(v == par[u]) continue;

		par[v] = u;
		edge_node[e] = v;
		node_edge[v] = e;

		dfs(v);

		subtree[u] += subtree[v];
	}
}

vi BIT(1 + mx, 0);



vi label_data(1 + mx, 1);
vi par_data(1 + mx, 0);
vi par_enabled(1 + mx, 0);


void bitadd(int i, int v)
{
	for(int j = i; j <= N; j += j&-j)
		BIT[j] += v;
}


int getblocked(int u)
{
	int p = ord_ind[u];
	int res = 0;
	for(int i = p; i >= 1; i -= i&-i)
		res += BIT[i];
	return res;
}

int getlabel(int u)
{
	int ub = getblocked(u);

	for(int e = lg; e >= 0; e--)
	{
		int v = anc[u][e];
		if(v == 0) continue;
		if(getblocked(v) != ub) continue;
		u = v;
	}

	return u;
}



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

	cin >> N >> M >> Q;

	for(int e = 1; e <= N-1; e++)
	{
		int x, y;
		cin >> x >> y;
		edge[x].push_back({y, e});
		edge[y].push_back({x, e});
	}

	dfs(1);


	anc[0][0] = 0;
	for(int i = 1; i <= N; i++) anc[i][0] = par[i];
	for(int e = 1; e <= lg; e++)
		for(int i = 0; i <= N; i++)
			anc[i][e] = anc[ anc[i][e-1] ][e-1];

	for(int u = 1; u <= N; u++)
	{
		bitadd(ord_ind[u], +1);
		bitadd(ord_ind[u] + subtree[u], -1);
	}


	for(int o = 1; o <= M; o++)
	{
		int e;
		cin >> e;

		int u = edge_node[e];

		if(par_enabled[u])
		{
			int glu = getlabel(u);

			par_data[u] = label_data[glu];
			par_enabled[u] = 0;

			label_data[u] = label_data[glu];

			bitadd(ord_ind[u], +1);
			bitadd(ord_ind[u] + subtree[u], -1);
		}
		else
		{
			int glpu = getlabel(par[u]);

			par_enabled[u] = 1;

			label_data[glpu] = label_data[glpu] + label_data[u] - par_data[u];

			bitadd(ord_ind[u], -1);
			bitadd(ord_ind[u] + subtree[u], +1);
		}
	}



	for(int q = 1; q <= Q; q++)
	{
		int C;
		cin >> C;

		cout << label_data[getlabel(C)] << '\n';
	}
}

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