oj.uz

Submission #1106541

# Submission time Handle Problem Language Result Execution time Memory
1106541 2024-10-30T15:53:00 Z xnqs Synchronization (JOI13_synchronization) C++17
100 / 100
 204 ms 26964 KB 
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>

template<typename Type>
class FenwickTree {
private:
	std::vector<Type> bit;
public:
	FenwickTree(int size = 0, Type val = 0) {
		Assign(size,val);
	}

	void Assign(int size = 0, Type val = 0) {
		bit.assign(size+1,0);
		for (int i = 1; i <= size; i++) {
			bit[i] += val;
			if (i+(i&-i)<=size) {
				bit[i+(i&-i)] += bit[i];
			}
		}
	}

	void Add(int pos, Type val) {
		while (pos<bit.size()) {
			bit[pos] += val;
			pos += pos&-pos;
		}
	}

	void Add(int l, int r, Type val) {
		Add(l, val);
		Add(r+1, -val);
	}

	Type Query(int pos) {
		Type ret = 0;
		while (pos>0) {
			ret += bit[pos];
			pos ^= pos&-pos;
		}
		return ret;
	}

	Type Query(int l, int r) {
		return Query(r) - Query(l-1);
	}

	int LowerBound(Type val) {
		int ret = 0;
		for (int step = (1<<(31-__builtin_clz((int)bit.size()))); step; step >>= 1) {
			if (ret+step<bit.size()&&val-bit[ret+step]>0) {
				val -= bit[ret+step];
				ret += step;
			}
		}
		return ret+1;
	}
	
	int UpperBound(Type val) {
		int ret = 0;
		for (int step = (1<<(31-__builtin_clz((int)bit.size()))); step; step >>= 1) {
			if (ret+step<bit.size()&&val-bit[ret+step]>=0) {
				val -= bit[ret+step];
				ret += step;
			}
		}
		return ret+1;
	}
};

int gs, q1, q2;
std::vector<std::vector<int>> adj_list;
std::vector<std::pair<int,int>> edges;
int depth[100005];
int up[17][100005];
int tin[100005];
int tout[100005];
int ans[100005];
int last_val[100005];
bool activated[100005];
FenwickTree<int> fnwk(200005,0);

void dfs(int k, int p, int& timer) {
	depth[k] = depth[p]+1;
	up[0][k] = p;
	tin[k] = tout[k] = ++timer;
	for (int j = 1; j < 17; j++) {
		up[j][k] = up[j-1][up[j-1][k]];
	}

	for (const auto& i : adj_list[k]) {
		if (i!=p) {
			dfs(i,k,timer);
			tout[k] = ++timer;
		}
	}
}

int get_root(int node) {
	for (int lvl = 16; lvl >= 0; lvl--) {
		if (!up[lvl][node]) {
			continue;
		}

		if (fnwk.Query(tin[up[lvl][node]]) == fnwk.Query(tin[node])) {
			node = up[lvl][node];
		}
	}
	
	return node;
}

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

	std::cin >> gs >> q1 >> q2;
	edges.reserve(gs-1);
	adj_list.resize(gs+1);
	for (int i = 0, a, b; i < gs-1; i++) {
		std::cin >> a >> b;
		adj_list[a].emplace_back(b);
		adj_list[b].emplace_back(a);
		edges.emplace_back(a,b);
	}

	{ int timer = 0; dfs(1,0,timer); }
	for (int i = 1; i <= gs; i++) {
		ans[i] = 1;
		fnwk.Add(tin[i], tout[i], 1);
	}

	while (q1--) {
		int idx;
		std::cin >> idx; --idx;

		auto [a, b] = edges[idx];
		if (tin[a]>tin[b]) {
			std::swap(a,b);
		}

		if (!activated[idx]) {
			int root = get_root(a);
			int new_val = ans[root] + ans[b] - last_val[idx];
			ans[root] = new_val;
			fnwk.Add(tin[b],tout[b],-1);
		}
		else {
			ans[b] = last_val[idx] = ans[get_root(a)];
			fnwk.Add(tin[b],tout[b],1);
		}

		activated[idx] ^= 1;
	}

	while (q2--) {
		int k;
		std::cin >> k;
		std::cout << ans[get_root(k)] << "\n";
	}
}

Compilation message

synchronization.cpp: In instantiation of 'void FenwickTree<Type>::Add(int, Type) [with Type = int]':
synchronization.cpp:35:6:   required from 'void FenwickTree<Type>::Add(int, int, Type) [with Type = int]'
synchronization.cpp:135:30:   required from here
synchronization.cpp:28:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |   while (pos<bit.size()) {
      |          ~~~^~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1360 KB Output is correct
2 Correct 2 ms 1104 KB Output is correct
3 Correct 2 ms 1104 KB Output is correct
4 Correct 2 ms 1360 KB Output is correct
5 Correct 2 ms 1360 KB Output is correct
6 Correct 2 ms 1360 KB Output is correct
7 Correct 11 ms 3052 KB Output is correct
8 Correct 11 ms 2896 KB Output is correct
9 Correct 12 ms 2896 KB Output is correct
10 Correct 137 ms 18480 KB Output is correct
11 Correct 106 ms 18504 KB Output is correct
12 Correct 177 ms 26184 KB Output is correct
13 Correct 59 ms 18368 KB Output is correct
14 Correct 77 ms 17736 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 22188 KB Output is correct
2 Correct 86 ms 21972 KB Output is correct
3 Correct 74 ms 25672 KB Output is correct
4 Correct 75 ms 25508 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7248 KB Output is correct
2 Correct 2 ms 7248 KB Output is correct
3 Correct 2 ms 7248 KB Output is correct
4 Correct 2 ms 7248 KB Output is correct
5 Correct 2 ms 7248 KB Output is correct
6 Correct 3 ms 7504 KB Output is correct
7 Correct 14 ms 9204 KB Output is correct
8 Correct 204 ms 26964 KB Output is correct
9 Correct 195 ms 26956 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 202 ms 26952 KB Output is correct
2 Correct 108 ms 26696 KB Output is correct
3 Correct 108 ms 26696 KB Output is correct
4 Correct 108 ms 26704 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7248 KB Output is correct
2 Correct 2 ms 7248 KB Output is correct
3 Correct 2 ms 7396 KB Output is correct
4 Correct 2 ms 7416 KB Output is correct
5 Correct 3 ms 7504 KB Output is correct
6 Correct 12 ms 8528 KB Output is correct
7 Correct 122 ms 19412 KB Output is correct
8 Correct 195 ms 26952 KB Output is correct
9 Correct 61 ms 19540 KB Output is correct
10 Correct 92 ms 19016 KB Output is correct
11 Correct 75 ms 23368 KB Output is correct
12 Correct 74 ms 23368 KB Output is correct
13 Correct 109 ms 26804 KB Output is correct