oj.uz

Submission #647779

# Submission time Handle Problem Language Result Execution time Memory
647779 2022-10-04T05:52:06 Z ymm Synchronization (JOI13_synchronization) C++17
100 / 100
 295 ms 42556 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 22196 KB Output is correct
2 Correct 13 ms 22228 KB Output is correct
3 Correct 12 ms 22228 KB Output is correct
4 Correct 12 ms 22260 KB Output is correct
5 Correct 12 ms 22208 KB Output is correct
6 Correct 13 ms 22360 KB Output is correct
7 Correct 30 ms 24052 KB Output is correct
8 Correct 28 ms 24008 KB Output is correct
9 Correct 26 ms 24020 KB Output is correct
10 Correct 270 ms 41452 KB Output is correct
11 Correct 263 ms 41480 KB Output is correct
12 Correct 268 ms 41632 KB Output is correct
13 Correct 241 ms 41080 KB Output is correct
14 Correct 142 ms 33392 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 37308 KB Output is correct
2 Correct 110 ms 37048 KB Output is correct
3 Correct 85 ms 33396 KB Output is correct
4 Correct 86 ms 33344 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 22260 KB Output is correct
2 Correct 13 ms 22228 KB Output is correct
3 Correct 13 ms 22168 KB Output is correct
4 Correct 12 ms 22228 KB Output is correct
5 Correct 12 ms 22244 KB Output is correct
6 Correct 15 ms 22328 KB Output is correct
7 Correct 30 ms 24188 KB Output is correct
8 Correct 285 ms 42520 KB Output is correct
9 Correct 289 ms 42556 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 294 ms 42444 KB Output is correct
2 Correct 96 ms 34544 KB Output is correct
3 Correct 98 ms 34716 KB Output is correct
4 Correct 106 ms 34668 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 22228 KB Output is correct
2 Correct 12 ms 22228 KB Output is correct
3 Correct 11 ms 22228 KB Output is correct
4 Correct 11 ms 22252 KB Output is correct
5 Correct 13 ms 22436 KB Output is correct
6 Correct 28 ms 24152 KB Output is correct
7 Correct 283 ms 42536 KB Output is correct
8 Correct 266 ms 42476 KB Output is correct
9 Correct 295 ms 42440 KB Output is correct
10 Correct 145 ms 34748 KB Output is correct
11 Correct 127 ms 38672 KB Output is correct
12 Correct 131 ms 38592 KB Output is correct
13 Correct 100 ms 34664 KB Output is correct