Submission #685014

#	Time	Username	Problem	Language	Result	Execution time	Memory
685014		flappybird	Synchronization (JOI13_synchronization)	C++17	30 / 100	8093 ms	54616 KiB

synchronization

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define MAX 202020
#define MAXS 20
#define INF 1000000000000000001
#define bb ' '
#define ln '\n'
#define Ln '\n'
pii edges[MAX];
vector<pii> toggle[MAX];
int laston[MAX];
vector<int> adj[MAX];
int ans[MAX];
int vis[MAX];
int num[MAX];
map<int, int> mp[MAX];
int findnxt(int v, int e) { return edges[e].first + edges[e].second - v; }
map<int, int> mpall;
int mpsum;
void bottomup(int x, int p = 0, int isrt = 0) {
	mp[x].clear();
	mp[x][0] = 1;
	int i;
	for (auto e : adj[x]) {
		int v = findnxt(x, e);
		if (vis[v] || v == p) continue;
		if (toggle[e].empty()) continue;
		bottomup(v, x);
		for (i = 0; i < toggle[e].size(); i++) {
			int s;
			if (i) s = toggle[e][i - 1].second;
			else s = -1;
			int nxt = toggle[e][i].first;
			while (1) {
				auto it = mp[v].lower_bound(s);
				if (it == mp[v].end()) break;
				if (it->first >= nxt) break;
				mp[v][nxt] += it->second;
				mp[v].erase(it);
			}
		}
		while (mp[v].size() && mp[v].rbegin()->first >= toggle[e].back().second) mp[v].erase(mp[v].rbegin()->first);
		if (!isrt) {
			if (mp[v].size() > mp[x].size()) swap(mp[v], mp[x]);
			for (auto& [a, b] : mp[v]) mp[x][a] += b;
		}
	}
}
void topdown(int x, int p) {
	ans[x] += mpsum;
	int i;
	for (auto e : adj[x]) {
		int v = findnxt(x, e);
		if (vis[v] || v == p) continue;
		if (toggle[e].empty()) continue;
		vector<pii> logv;
		for (i = 0; i < toggle[e].size(); i++) {
			int s;
			if (i) s = toggle[e][i - 1].second;
			else s = -1;
			int nxt = toggle[e][i].first;
			while (1) {
				auto it = mpall.lower_bound(s);
				if (it == mpall.end()) break;
				if (it->first >= nxt) break;
				logv.emplace_back(it->first, it->second);
				logv.emplace_back(nxt, -it->second);
				mpall[nxt] += it->second;
				mpall.erase(it);
			}
		}
		while (mpall.size() && mpall.rbegin()->first >= toggle[e].back().second) {
			mpsum -= mpall.rbegin()->second;
			logv.emplace_back(mpall.rbegin()->first, mpall.rbegin()->second);
			mpall.erase(mpall.rbegin()->first);
		}
		topdown(v, x);
		for (auto& [a, b] : logv) mpall[a] += b, mpsum += b;
	}
}
void make_num(int x, int p = 0) {
	mp[x].clear();
	num[x] = 1;
	for (auto e : adj[x]) {
		int v = findnxt(x, e);
		if (v == p || vis[v]) continue;
		make_num(v, x);
		num[x] += num[v];
	}
}
void make_tree(int x) {
	make_num(x);
	int c = x;
	int n = num[x];
	while (1) {
		int changed = 0;
		for (auto e : adj[c]) {
			int v = findnxt(c, e);
			if (!vis[v] && num[v] < num[c]) {
				if (num[v] > n / 2) {
					c = v;
					changed = 1;
					break;
				}
			}
		}
		if (!changed) break;
	}
	bottomup(c, 0, 1);
	mpall.clear();
	mpsum = 0;
	for (auto e : adj[c]) {
		int v = findnxt(c, e);
		if (vis[v]) continue;
		for (auto& [a, b] : mp[v]) if (b) mpall[a] += b, mpsum += b;
	}
	for (auto& [a, b] : mp[c]) if (b) mpall[a] += b, mpsum += b;
	ans[c] += mpsum;
	int i;
	for (auto e : adj[c]) {
		int v = findnxt(c, e);
		if (vis[v]) continue;
		if (toggle[e].empty()) continue;
		for (auto& [a, b] : mp[v]) if (b) mpall[a] -= b, mpsum -= b;
		vector<pii> logv;
		for (i = 0; i < toggle[e].size(); i++) {
			int s;
			if (i) s = toggle[e][i - 1].second;
			else s = -1;
			int nxt = toggle[e][i].first;
			while (1) {
				auto it = mpall.lower_bound(s);
				if (it == mpall.end()) break;
				if (it->first >= nxt) break;
				logv.emplace_back(it->first, it->second);
				logv.emplace_back(nxt, -it->second);
				mpall[nxt] += it->second;
				mpall.erase(it);
			}
		}
		while (mpall.size() && mpall.rbegin()->first >= toggle[e].back().second) {
			mpsum -= mpall.rbegin()->second;
			logv.emplace_back(mpall.rbegin()->first, mpall.rbegin()->second);
			mpall.erase(mpall.rbegin()->first);
		}
		topdown(v, c);
		for (auto& [a, b] : logv) mpall[a] += b, mpsum += b;
		for (auto& [a, b] : mp[v]) if (b) mpall[a] += b, mpsum += b;
	}
	vis[c] = 1;
	for (auto e : adj[c]) {
		int v = findnxt(c, e);
		if (!vis[v]) make_tree(v);
	}
}
signed main() {
	ios::sync_with_stdio(false), cin.tie(0);
	int N, M, Q;
	cin >> N >> M >> Q;
	int i, a, b;
	for (i = 1; i < N; i++) {
		cin >> a >> b;
		edges[i] = pii(a, b);
		adj[a].push_back(i);
		adj[b].push_back(i);
	}
	for (i = 1; i <= M; i++) {
		cin >> a;
		if (laston[a]) {
			toggle[a].emplace_back(laston[a], i);
			laston[a] = 0;
		}
		else laston[a] = i;
	}
	for (i = 1; i < N; i++) if (laston[i]) toggle[i].emplace_back(laston[i], M + 1);
	make_tree(1);
	vector<int> qs;
	while (Q--) {
		cin >> a;
		qs.push_back(a);
	}
	for (auto v : qs) cout << ans[v] << ln;
}

Compilation message (stderr)

synchronization.cpp: In function 'void bottomup(int, int, int)':
synchronization.cpp:36:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |   for (i = 0; i < toggle[e].size(); i++) {
      |               ~~^~~~~~~~~~~~~~~~~~
synchronization.cpp: In function 'void topdown(int, int)':
synchronization.cpp:64:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |   for (i = 0; i < toggle[e].size(); i++) {
      |               ~~^~~~~~~~~~~~~~~~~~
synchronization.cpp: In function 'void make_tree(int)':
synchronization.cpp:133:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  133 |   for (i = 0; i < toggle[e].size(); i++) {
      |               ~~^~~~~~~~~~~~~~~~~~

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