oj.uz

Submission #600485

# Submission time Handle Problem Language Result Execution time Memory
600485 2022-07-20T22:34:40 Z GusterGoose27 Synchronization (JOI13_synchronization) C++11
100 / 100
 501 ms 61360 KB 
#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;

class upd {
public:
	int a, b;
	int id;
	upd(int an, int bn, int i) {
		a = an;
		b = bn;
		id = i;
	}
	upd() {}
};

const int MAXN = 1e5;
const int MAXM = 2e5;
bitset<MAXN> bsets[MAXN];
int last_sync[MAXN]; // edges
int info[MAXN];
int uf[MAXN];
int ufrank[MAXN];
vector<int> par_set;
vector<int> ufrank_set;
int n, m, q;
upd edges[MAXN];

int find(int i) {
	return (uf[i] == -1) ? i : find(uf[i]);
}

void merge(upd &u) {
	int r1 = find(u.a);
	int r2 = find(u.b);
	if (ufrank[r1] > ufrank[r2]) {
		int temp = r1; r1 = r2; r2 = temp;
	}
	par_set.push_back(r1);
	uf[r1] = r2;
	info[r2] += info[r1]-last_sync[u.id];
	if (ufrank[r1] == ufrank[r2]) {
		ufrank[r2]++;
		ufrank_set.push_back(r2);
	}
	else ufrank_set.push_back(-1);
}

class stree {
public:
	int lt, rt;
	stree *l = nullptr;
	stree *r = nullptr;
	vector<upd> merges;
	stree(int lp, int rp) {
		lt = lp;
		rt = rp;
		if (rp > lp) {
			int m = (lt+rt)/2;
			l = new stree(lt, m);
			r = new stree(m+1, rt);
		}
	}
	void update(upd &m, int lm, int rm) {
		if (lt > rm || rt < lm) return;
		if (lt >= lm && rt <= rm) {
			merges.push_back(m);
			return;
		}
		l->update(m, lm, rm);
		r->update(m, lm, rm);
	}
	void dfs() {
		for (upd u: merges) merge(u);
		if (l) l->dfs();
		if (r) r->dfs();
		for (int i = merges.size()-1; i >= 0; i--) {
			int p = par_set.back();
			par_set.pop_back();
			int r = ufrank_set.back();
			ufrank_set.pop_back();
			info[p] = info[uf[p]];
			last_sync[merges[i].id] = info[p];
			uf[p] = -1;
			if (r >= 0) ufrank[r]--;
		}
	}
};

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> n >> m >> q;
	for (int i = 0; i < n-1; i++) {
		int x, y; cin >> x >> y; x--; y--;
		edges[i] = upd(x, y, i);
	}
	map<int, int> prev;
	stree *tree = new stree(0, m-1);
	fill(uf, uf+n, -1);
	fill(info, info+n, 1);
	for (int i = 0; i < m; i++) {
		int x; cin >> x; x--;
		if (prev.find(x) == prev.end()) prev[x] = i;
		else {
			tree->update(edges[x], prev[x], i);
			prev.erase(x);
		}
	}
	for (auto val: prev) {
		tree->update(edges[val.first], val.second, m-1);
	}
	tree->dfs();
	for (int i = 0; i < q; i++) {
		int x; cin >> x; x--;
		cout << info[find(x)] << "\n";
	}
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 3 ms 724 KB Output is correct
7 Correct 32 ms 5908 KB Output is correct
8 Correct 27 ms 5908 KB Output is correct
9 Correct 26 ms 5948 KB Output is correct
10 Correct 447 ms 60548 KB Output is correct
11 Correct 500 ms 60320 KB Output is correct
12 Correct 415 ms 60536 KB Output is correct
13 Correct 441 ms 59440 KB Output is correct
14 Correct 207 ms 36724 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 53756 KB Output is correct
2 Correct 186 ms 52600 KB Output is correct
3 Correct 115 ms 36356 KB Output is correct
4 Correct 117 ms 36380 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 4 ms 852 KB Output is correct
7 Correct 32 ms 5916 KB Output is correct
8 Correct 435 ms 61220 KB Output is correct
9 Correct 440 ms 61360 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 442 ms 61040 KB Output is correct
2 Correct 144 ms 37384 KB Output is correct
3 Correct 133 ms 37572 KB Output is correct
4 Correct 147 ms 37540 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 3 ms 852 KB Output is correct
6 Correct 31 ms 6036 KB Output is correct
7 Correct 441 ms 61104 KB Output is correct
8 Correct 501 ms 61148 KB Output is correct
9 Correct 448 ms 60744 KB Output is correct
10 Correct 245 ms 37956 KB Output is correct
11 Correct 180 ms 54888 KB Output is correct
12 Correct 166 ms 54992 KB Output is correct
13 Correct 173 ms 37580 KB Output is correct