oj.uz

Submission #84973

# Submission time Handle Problem Language Result Execution time Memory
84973 2018-11-17T21:00:23 Z radoslav11 Synchronization (JOI13_synchronization) C++14
100 / 100
 313 ms 90832 KB 
/*
	Let's imagine that we never remove edges. This means that we can solve the problem with a simple dsu (we will keep the sizes of the components). To solve this version we will use link-cut tree.
	For each component we will keep the "answer" for its root. Obviously at the current time the answers will be the same the vertices in one component. So when we merge we will only add the values.
	Unfortunately this is wrong as the components we merge might have common vertices. But we can easily fix it by exploiting the tree structure of the graph. For each edge we will keep the size of
	the component when we last cut it. Let this number for an edge E be C(E). Then when we again add edge E to the graph, the new answer will be Answer(E.u) + Answer(E.v) - C(E). We mustn't forget
	to change C(E) when we again remove E.

	As I don't like implementing link-cut trees with splay tree, the theoretical complexity will be O(N log^2 N). However, in practice implementing them with treaps has the same speed and sometimes 
	is even faster. That's because the rotations of splay trees are slow.
*/

#include <bits/stdc++.h>
#define endl '\n'

//#pragma GCC optimize ("O3")
//#pragma GCC target ("sse4")

#define SZ(x) ((int)x.size())
#define ALL(V) V.begin(), V.end()
#define L_B lower_bound
#define U_B upper_bound

using namespace std;
template<class T, class T2> inline int chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline int chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }
const int MAXN = (1 << 20);

random_device rd;
mt19937 mt(rd());

struct node
{
	int id, sz, prior;
	node *l, *r, *par, *pp;

	node() { id = sz = prior = 0; l = r = par = pp = nullptr; }
	node(int _i)
	{
		id = _i;
		prior = mt();
		sz = 1;
		l = r = par = pp = nullptr;
	}
};

using pnode = node*;

inline int size(pnode t) { return t ? t->sz : 0; }

void pull(pnode &t)
{
	if(!t) return;
	t->sz = 1 + size(t->l) + size(t->r);
	
	t->par = nullptr;
	
	if(t->l) t->l->par = t;
	if(t->r) t->r->par = t;

	if(t->l && t->l->pp) t->pp = t->l->pp, t->l->pp = nullptr;
	if(t->r && t->r->pp) t->pp = t->r->pp, t->r->pp = nullptr;
}

void merge(pnode &t, pnode l, pnode r)
{
	if(!l) { t = r; pull(t); return; }
	if(!r) { t = l; pull(t); return; }

	if(l->prior > r->prior)
		merge(l->r, l->r, r), t = l;
	else
		merge(r->l, l, r->l), t = r;

	pull(t);
}

void split_sz(pnode t, pnode &l, pnode &r, int k, int add = 0)
{
	if(!t) { l = nullptr; r = nullptr; return; }

	int idx = add + size(t->l);
	if(idx <= k)
		split_sz(t->r, t->r, r, k, idx + 1), l = t;
	else
		split_sz(t->l, l, t->l, k, add), r = t;

	pull(t);
}

int get_pos(pnode t)
{
	if(!t) return 0;

	int ret = size(t->l);
	while(t->par)
	{
		if(t->par->r == t)
			ret += 1 + size(t->par->l);
		t = t->par;
	}

	return ret;
}

pnode treap_root(pnode t) { while(t->par) t = t->par; return t; }

pnode remove_after(pnode v)
{
	pnode root = treap_root(v), L, R, prv_pp = root->pp;
	root->pp = nullptr;
	
	split_sz(root, L, R, get_pos(v));
	if(R) R->pp = v;
	L->pp = prv_pp;
	return L;
}

void access(pnode v)
{
	v = remove_after(v);
	while(v->pp)
	{
		auto pr = v->pp;
		v->pp = nullptr;
		pr = remove_after(pr);
		merge(v, pr, v);
	}
}

int n, m, q;
pair<int, int> ed[MAXN];

void read()
{	
	cin >> n >> m >> q;
	for(int i = 1; i <= n - 1; i++)
		cin >> ed[i].first >> ed[i].second;
}

int last[MAXN];
int state_e[MAXN];
int ans[MAXN];
pnode ver[MAXN];

int dep[MAXN];
vector<int> adj[MAXN];

void pre_dfs(int u, int pr = -1, int d = 0)
{
	dep[u] = d;
	for(int v: adj[u])
		if(v != pr)
			pre_dfs(v, u, d + 1);
}

int root(int u)
{
	access(ver[u]);
	auto p = treap_root(ver[u]);
	while(p->l) p = p->l;
	return p->id;
}

void cut(int u, int v)
{
	if(dep[u] < dep[v]) swap(u, v);
	access(ver[u]);
	access(ver[v]);
	treap_root(ver[u])->pp = nullptr;
}

void link(int u, int v)
{
	if(dep[u] < dep[v]) swap(u, v);
	access(ver[u]);
	treap_root(ver[u])->pp = ver[v];
}

void solve()
{
	for(int i = 1; i < n; i++)
	{
		adj[ed[i].first].push_back(ed[i].second);
		adj[ed[i].second].push_back(ed[i].first);
	}

	pre_dfs(1);
	for(int i = 1; i <= n; i++)
		ans[i] = 1, ver[i] = new node(i);

	while(m--)
	{
		int i;
		cin >> i;

		state_e[i] ^= 1;

		if(state_e[i] == 0)
		{
			last[i] = ans[root(ed[i].first)];
			cut(ed[i].first, ed[i].second);

			ans[root(ed[i].first)] = last[i];
			ans[root(ed[i].second)] = last[i];
		}
		else
		{
			int nw = ans[root(ed[i].first)] + ans[root(ed[i].second)] - last[i];
			link(ed[i].first, ed[i].second);
			
			ans[root(ed[i].first)] = nw;
		}
	}

	while(q--)
	{
		int u;
		cin >> u;
		cout << ans[root(u)] << endl;
	}
}

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

	read();
	solve();
	return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 24952 KB Output is correct
2 Correct 24 ms 25204 KB Output is correct
3 Correct 25 ms 25288 KB Output is correct
4 Correct 23 ms 25340 KB Output is correct
5 Correct 24 ms 25340 KB Output is correct
6 Correct 24 ms 25376 KB Output is correct
7 Correct 36 ms 26872 KB Output is correct
8 Correct 37 ms 26968 KB Output is correct
9 Correct 36 ms 27192 KB Output is correct
10 Correct 203 ms 40828 KB Output is correct
11 Correct 185 ms 43236 KB Output is correct
12 Correct 176 ms 50220 KB Output is correct
13 Correct 140 ms 50220 KB Output is correct
14 Correct 146 ms 50220 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 183 ms 51376 KB Output is correct
2 Correct 166 ms 53160 KB Output is correct
3 Correct 142 ms 57120 KB Output is correct
4 Correct 144 ms 58904 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 58904 KB Output is correct
2 Correct 25 ms 58904 KB Output is correct
3 Correct 25 ms 58904 KB Output is correct
4 Correct 24 ms 58904 KB Output is correct
5 Correct 24 ms 58904 KB Output is correct
6 Correct 26 ms 58904 KB Output is correct
7 Correct 39 ms 58904 KB Output is correct
8 Correct 224 ms 62724 KB Output is correct
9 Correct 203 ms 65524 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 212 ms 65564 KB Output is correct
2 Correct 212 ms 67720 KB Output is correct
3 Correct 210 ms 70128 KB Output is correct
4 Correct 219 ms 72504 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 72504 KB Output is correct
2 Correct 25 ms 72504 KB Output is correct
3 Correct 26 ms 72504 KB Output is correct
4 Correct 31 ms 72504 KB Output is correct
5 Correct 25 ms 72504 KB Output is correct
6 Correct 42 ms 72504 KB Output is correct
7 Correct 226 ms 72504 KB Output is correct
8 Correct 198 ms 78524 KB Output is correct
9 Correct 204 ms 78524 KB Output is correct
10 Correct 313 ms 78844 KB Output is correct
11 Correct 237 ms 84028 KB Output is correct
12 Correct 254 ms 86572 KB Output is correct
13 Correct 207 ms 90832 KB Output is correct