Submission #647779

#	Time	Username	Problem	Language	Result	Execution time	Memory
647779		ymm	Synchronization (JOI13_synchronization)	C++17	100 / 100	295 ms	42556 KiB

synchronization

#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

const int N = 200'010;

int ev[N], eu[N];
int e_last_inter[N];
int cnt_info[N];
int change[N];
int query[N];
int n, m, q;

namespace dsu {
int par[N], sz[N];
vector<tuple<int,int,int>> history;

int root(int v) { return par[v] == -1? v: root(par[v]); }
void unite(int v, int u, int e)
{
	v = root(v);
	u = root(u);
	assert(v != u);
	if (sz[v] < sz[u])
		swap(v, u);
	history.emplace_back(v, u, e);
	par[u] = v;
	sz[v] += sz[u];
	cnt_info[v] = cnt_info[v] + cnt_info[u] - e_last_inter[e];
	//printf("%d became child of %d, %d's cnt_info updated to %d\n",
	//       u, v, v, cnt_info[v]);
}

void revert()
{
	auto [v, u, e] = history.back();
	history.pop_back();
	e_last_inter[e] = cnt_info[v];
	cnt_info[u] = cnt_info[v];
	sz[v] -= sz[u];
	par[u] = -1;
	//printf("%d got seperated from %d, %d's cnt_info updated to %d\n",
	//       u, v, u, cnt_info[u]);
}

void init()
{
	fill(par, par+N, -1);
	fill(sz, sz+N, 1);
	history.clear();
}
}

namespace dyn_con {
vector<int> seg[N<<2];

void place(int l, int r, int edge, int i, int b, int e)
{
	if (l <= b && e <= r) {
		seg[i].push_back(edge);
		return;
	}
	if (r <= b || e <= l)
		return;
	place(l,r,edge,2*i+1,b,(b+e)/2);
	place(l,r,edge,2*i+2,(b+e)/2,e);
}

void dfs(int i, int b, int e)
{
	for (int e : seg[i])
		dsu::unite(ev[e], eu[e], e);
	if (e-b > 1) {
		dfs(2*i+1,b,(b+e)/2);
		dfs(2*i+2,(b+e)/2,e);
	}
	for (int e : seg[i])
		dsu::revert();
}
}

void make_dyn()
{
	static int last[N];
	memset(last, -1, sizeof(last));
	Loop (i,0,m) {
		if (last[change[i]] == -1) {
			last[change[i]] = i;
		} else {
			dyn_con::place(last[change[i]], i, change[i],
			               0, 0, m);
			last[change[i]] = -1;
		}
	}
	Loop (i,0,n-1) {
		if (last[i] != -1)
			dyn_con::place(last[i], m, i, 0, 0, m);
	}
}

void input()
{
	cin >> n >> m >> q;
	Loop (i,0,n-1) {
		cin >> ev[i] >> eu[i];
		--ev[i];
		--eu[i];
	}
	Loop (i,0,m) {
		cin >> change[i];
		--change[i];
	}
	Loop (i,0,q) {
		cin >> query[i];
		--query[i];
	}
}

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	input();
	make_dyn();
	dsu::init();
	fill(cnt_info, cnt_info+N, 1);
	dyn_con::dfs(0, 0, m);
	Loop (i,0,q)
		cout << cnt_info[query[i]] << '\n';
}

Compilation message (stderr)

synchronization.cpp: In function 'void dyn_con::dfs(int, int, int)':
synchronization.cpp:81:11: warning: unused variable 'e' [-Wunused-variable]
   81 |  for (int e : seg[i])
      |           ^

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