Submission #1221406

#	Time	Username	Problem	Language	Result	Execution time	Memory
1221406		colossal_pepe	Synchronization (JOI13_synchronization)	C++20	20 / 100	66 ms	47176 KiB

synchronization

#include <bits/stdc++.h>
using namespace std;

// DEBUG TOOLS

#ifdef _LOCAL
#define LOG(msg) cerr << "DEBUG: " << msg << endl
#else
#define LOG(msg)
#endif

// DEBUG TOOLS

int n, m, q;
vector<vector<pair<int, int>>> g;
vector<vector<pair<int, int>>> et;
vector<int> roots;

bool bad() {
	long long x = (long long)n * (long long)q;
	return x > (long long)1e8;
}

vector<int> solve(int root) {
	multiset<int> s = {0};
	auto dfs = [&s](const auto& self, int u, int par, map<int, int> m_cur) -> void {
		for (auto [i, v] : g[u]) {
			if (v == par) continue;
			LOG("BRUH KOTHAY " << i << ' ' << v);
			map<int, int> m_nxt;
			for (auto [l, r] : et[i]) {
				LOG("HELLO " << u << ' ' << v << ' ' << l << ' ' << r);
				auto itr = m_cur.lower_bound(l);
				if (itr == m_cur.end()) continue;
				m_nxt[r] = max(itr->second, l);
			}
			LOG("UMM");
			if (m_nxt.empty()) continue;
			s.insert(m_nxt.begin()->second);
			LOG("SHESH");
			self(self, v, u, m_nxt);
		}
	};
	dfs(dfs, root, -1, {{m + 1, 0}});
	vector<int> ret(s.begin(), s.end());
	return ret;
}



int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n >> m >> q;
	if (bad()) return 0;
	g.resize(n);
	for (int i = 0; i < n - 1; i++) {
		int u, v;
		cin >> u >> v;
		u--, v--;
		g[u].push_back(make_pair(i, v));
		g[v].push_back(make_pair(i, u));
	}
	et.resize(n - 1);
	for (int i = 1; i <= m; i++) {
		int j;
		cin >> j;
		j--;
		if (et[j].empty() or et[j].back().second != m + 1) et[j].push_back(make_pair(i, m + 1));
		else et[j].back().second = i;
	}
	roots.resize(q);
	for (int &v : roots) {
		cin >> v;
		v--;
		vector<int> ans = solve(v);
		cout << ans.size() << '\n';
	}
	return 0;
}

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