Submission #301287

#	Time	Username	Problem	Language	Result	Execution time	Memory
301287		mode149256	Synchronization (JOI13_synchronization)	C++17	100 / 100	635 ms	25836 KiB

synchronization

/*input
5 6 3
1 2
1 3
2 4
2 5
1
2
1
4
4
3
1
4
5
*/
#include <bits/stdc++.h>
using namespace std;

namespace my_template {
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<ld, ld> pd;

typedef vector<int> vi;
typedef vector<vi> vii;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<vl> vll;
typedef vector<pi> vpi;
typedef vector<vpi> vpii;
typedef vector<pl> vpl;
typedef vector<cd> vcd;
typedef vector<pd> vpd;
typedef vector<bool> vb;
typedef vector<vb> vbb;
typedef std::string str;
typedef std::vector<str> vs;

#define x first
#define y second
#define debug(...) cout<<"["<<#__VA_ARGS__<<": "<<__VA_ARGS__<<"]\n"

const ld PI = 3.14159265358979323846264338327950288419716939937510582097494L;

template<typename T>
pair<T, T> operator+(const pair<T, T> &a, const pair<T, T> &b) { return pair<T, T>(a.x + b.x, a.y + b.y); }
template<typename T>
pair<T, T> operator-(const pair<T, T> &a, const pair<T, T> &b) { return pair<T, T>(a.x - b.x, a.y - b.y); }
template<typename T>
T operator*(const pair<T, T> &a, const pair<T, T> &b) { return (a.x * b.x + a.y * b.y); }
template<typename T>
T operator^(const pair<T, T> &a, const pair<T, T> &b) { return (a.x * b.y - a.y * b.x); }

template<typename T>
void print(vector<T> vec, string name = "") {
	cout << name;
	for (auto u : vec)
		cout << u << ' ';
	cout << '\n';
}
}
using namespace my_template;

const int MOD = 1000000007;
const ll INF = std::numeric_limits<ll>::max();
const int MX = 100101;
const int LG = 23;

struct FENWICK {
	int N;
	vi A;
	FENWICK(int n) : N(n) {
		A.resize(n + 1, 0);
	}
	void add(int i, int x) {
		for (; i <= N; i += (i) & (-i))
			A[i] += x;
	}
	int get(int i) {
		int ret = 0;
		for (; i > 0; i -= (i) & (-i))
			ret += A[i];
		return ret;
	}
};

int N, M, Q;
vii edges(MX);
vpi visos;
vii p(LG, vi(MX, 0));
vi st(MX);
vi fn(MX);
vi ats(MX, 1);
vi perdaviau(MX, 0);
vi active(MX, 0);
FENWICK fen(1);
int piv = 1;

void dfs(int x, int par) {
	st[x] = piv++;
	p[0][x] = par;
	for (int i = 1; i < LG; ++i)
	{
		p[i][x] = p[i - 1][p[i - 1][x]];
	}

	for (auto u : edges[x]) {
		if (u == par) continue;
		dfs(u, x);
	}
	fn[x] = piv;
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> N >> M >> Q;
	for (int i = 0; i < N - 1; ++i)
	{
		int a, b;
		cin >> a >> b;
		visos.emplace_back(a, b);
		edges[a].emplace_back(b);
		edges[b].emplace_back(a);
	}

	dfs(1, 0);
	fen = FENWICK(N + 2);
	for (int i = 2; i <= N; ++i)
	{
		fen.add(st[i], 1);
		fen.add(fn[i], -1);
	}

	auto kiek = [&](int x) {
		return fen.get(x);
	};

	auto findRoot = [&](int x) -> int {
		int ret = x;
		for (int i = LG - 1; i >= 0; --i)
		{
			if (p[i][ret] and kiek(st[p[i][ret]]) == kiek(st[x])) {
				ret = p[i][ret];
			}
		}
		return ret;
	};

	for (int i = 0; i < M; ++i)
	{
		int ind; cin >> ind; ind--;
		int x = visos[ind].x;
		int y = visos[ind].y;

		if (p[0][x] == y) swap(x, y);
		// x
		// y
		if (active[ind]) {
			ats[y] = perdaviau[y] = ats[findRoot(x)];
			fen.add(st[y], 1);
			fen.add(fn[y], -1);
		} else {
			ats[findRoot(x)] += ats[y] - perdaviau[y];
			fen.add(st[y], -1);
			fen.add(fn[y], 1);
		}
		active[ind] ^= 1;
	}

	for (int i = 0; i < Q; ++i)
	{
		int a;
		cin >> a;
		printf("%d\n", ats[findRoot(a)]);
	}
}

/* Look for:
* special cases (n=1?)
* overflow (ll vs int?)
* the exact constraints (multiple sets are too slow for n=10^6 :( )
* array bounds
*/

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 10 / 10
• Subtask 4: 20 / 20
• Subtask 5: 40 / 40