Submission #374713

#	Time	Username	Problem	Language	Result	Execution time	Memory
374713		guka415	Mergers (JOI19_mergers)	C++14	0 / 100	149 ms	68192 KiB

mergers

#define fast ios::sync_with_stdio(false); cin.tie(0)
#define foru(i, k, n) for (int i = k; i < n; i++)
#define ford(i, k, n) for (int i = k; i >= n; i--)
#define pb push_back
#define mp make_pair

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
#include <bitset>

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

template<class T>
struct rmq {
	vector<vector<T>> a;
	vector<int> logs;
	int dep, len;
	rmq(vector<T> arr) {
		len = arr.size();
		dep = 0;
		int tmp = len;
		while (tmp) {
			tmp >>= 1;
			dep++;
		}
		a.resize(dep);
		foru(i, 0, dep) {
			a[i].resize(len);
			for (int j = 0; j + (1 << i) <= len; j++) {
				if (!i)a[i][j] = arr[j];
				else a[i][j] = min(a[i - 1][j], a[i - 1][j + (1 << (i - 1))]);
			}
		}
		initLogs();
	}
	void initLogs() {
		logs.resize(len + 1);
		logs[1] = 0;
		foru(i, 2, len + 1)logs[i] = logs[i >> 1] + 1;
	}
	T query(int l, int r) {
		int mylen = logs[r - l + 1];
		return min(a[mylen][l], a[mylen][r - (1 << mylen) + 1]);
	}
};
struct lca {
	vector<vector<int>> adj;
	vector<int> appear;
	vector<pii> dep;
	rmq<pii>* tree;
	int sz;
	lca(vector<vector<int>> adjacency) {
		adj = adjacency;
		sz = adjacency.size();
		appear.resize(sz);
		dfsscan(0, -1, 0);
		tree = new rmq<pii>(dep);
	}
	void dfsscan(int src, int prev, int currdep) {
		appear[src] = dep.size();
		dep.pb(mp(currdep, src));
		for (auto x : adj[src]) {
			if (x == prev)continue;
			dfsscan(x, src, currdep + 1);
			dep.pb(mp(currdep, src));
		}
	}
	int query(int a, int b) {
		int x = min(appear[a], appear[b]), y = max(appear[a], appear[b]);
		return tree->query(x, y).second;
	}
};

const int sz = 5e5 + 5;
int cntreg[sz], reg[sz], reglca[sz], n, k, dep[sz];
vector<vector<int>> adj;
vector<int> myreg[sz];
bitset<sz> isFull, isUpFull;

void dfsdep(int src, int prv) {
	for (int x : adj[src]) {
		if (x != prv) {
			dep[x] = dep[src] + 1;
			dfsdep(x, src);
		}
	}
}

int dfs(int src, int prv) {
	int curmaxlca = reglca[reg[src]];
	for (int x : adj[src]) {
		if (x != prv) {
			int tmp = dfs(x, src);
			if (dep[tmp] < dep[curmaxlca])
				curmaxlca = tmp;
		}
	}
	isFull[src] = (curmaxlca == src);
	return curmaxlca;
}

bool dfs2(int src, int prv) {
	bool found = 0;
	for (int x : adj[src]) {
		if (x != prv)
			found |= dfs2(x, src);
	}
	isUpFull[src] = (!found&&isFull[src]);
	return found || isFull[src];
}

int main() {
	fast;
	cin >> n >> k;
	adj.resize(n);
	foru(i, 0, n - 1) {
		int x, y;
		cin >> x >> y;
		adj[--x].pb(--y);
		adj[y].pb(x);
	}
	foru(i, 0, n)
		cin >> reg[i], cntreg[reg[i]]++, myreg[reg[i]].pb(i);
	dfsdep(0, -1);
	lca tre(adj);
	for (int i = 1; i <= k; i++) {
		reglca[i] = myreg[i][0];
		for (int j = 1; j < myreg[i].size(); j++)
			reglca[i] = tre.query(reglca[i], myreg[i][j]);
	}
	dfs(0, -1);
	dfs2(0, -1);
	isUpFull[0] = 0;
	if (adj[0].size() == 1)
		isUpFull[0] = isUpFull[adj[0][0]];
	cout << (isUpFull.count() + 1) / 2 << '\n';
	return 0;
}

Compilation message (stderr)

mergers.cpp: In function 'int main()':
mergers.cpp:135:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  135 |   for (int j = 1; j < myreg[i].size(); j++)
      |                   ~~^~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 24
• Subtask 3: 0 / 14
• Subtask 4: 0 / 22
• Subtask 5: 0 / 30