Submission #1106541

#	Time	Username	Problem	Language	Result	Execution time	Memory
1106541		xnqs	Synchronization (JOI13_synchronization)	C++17	100 / 100	204 ms	26964 KiB

synchronization

#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 (stderr)

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 / 10
• Subtask 2: 20 / 20
• Subtask 3: 10 / 10
• Subtask 4: 20 / 20
• Subtask 5: 40 / 40