Submission #347127

#	Time	Username	Problem	Language	Result	Execution time	Memory
347127		wwdd	Mergers (JOI19_mergers)	C++14	70 / 100	477 ms	78824 KiB

mergers

#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> ii;
const int MN = 200200;
const int LOG = 18;
class U {
	private:
		vi rk,p,lev,ro;
	public:
		U(const vi& w) {
			lev = w;
			rk.assign(w.size(),0);
			for(int i=0;i<w.size();i++) {
				p.push_back(i);
				ro.push_back(i);
			}
		}
		int find(int a) {
			if(a == p[a]) {return a;}
			return p[a] = find(p[a]);
		}
		bool same(int a, int b) {
			return find(a) == find(b);
		}
		bool un(int a, int b) {
			if(same(a,b)) {return false;}
			a = find(a);b = find(b);
			if(rk[a] < rk[b]) {swap(a,b);}
			if(rk[a] == rk[b]) {rk[a]++;}
			if(lev[a] > lev[b]) {
				ro[a] = ro[b];
			}
			lev[a] = min(lev[a],lev[b]);
			p[b] = a;
			return true;
		}
		int rep(int u) {
			return ro[find(u)];
		}
};
vi lev;
vvi g;
int pa[MN][LOG];
int en[MN],ex[MN];
int dord;
void dfa(int u, int p, int lu, vi& le) {
	pa[u][0] = p;
	lev[u] = lu;
	en[u] = dord;dord++;
	for(int i=0;i<g[u].size();i++) {
		int v = g[u][i];
		if(v == p) {continue;}
		dfa(v,u,lu+1,le);
	}
	ex[u] = dord;dord++;
}
void proc() {
	for(int j=1;j<LOG;j++) {
		for(int i=0;i<g.size();i++) {
			pa[i][j] = pa[pa[i][j-1]][j-1];
		}
	}
}
bool anc(int a, int b) {
	return en[a] <= en[b] && ex[a] >= ex[b];
}
int lca(int a, int b) {
	if(anc(a,b)) {return a;}
	if(anc(b,a)) {return b;}
	for(int i=LOG-1;i>=0;i--) {
		if(!anc(pa[a][i],b)) {
			a = pa[a][i];
		}
	}
	return pa[a][0];
}
int main() {
	int n,k;
	cin >> n >> k;
	g.assign(n,vi());
	lev.assign(n,0);
	dord = 0;
	vector<ii> eg;
	for(int i=1;i<n;i++) {
		int a,b;
		cin >> a >> b;
		a--;b--;
		g[a].push_back(b);
		g[b].push_back(a);
		eg.emplace_back(a,b);
	}
	dfa(0,0,0,lev);
	U bs(lev);
	proc();
	vvi bob(k,vi());
	for(int i=0;i<n;i++) {
		int co;
		cin >> co;
		co--;
		bob[co].push_back(i);
	}
	vi rob(n,0);
	for(int i=0;i<k;i++) {
		int sz = bob[i].size();
		for(int j=0;j<bob[i].size();j++) {
			int u = bob[i][j];
			int v = bob[i][(j+1)%sz];
			int lu = lca(u,v);
			rob[u] = max(rob[u],lev[u]-lev[lu]);
			rob[v] = max(rob[v],lev[v]-lev[lu]);
		}
	}
	for(int i=0;i<n;i++) {
		int gol = lev[i]-rob[i];
		int u = bs.rep(i);
		while(lev[u] > gol) {
			bs.un(u,pa[u][0]);
			u = bs.rep(u);
		}
	}
	vector<set<int>> ha(n);
	for(int i=0;i<eg.size();i++) {
		int a = bs.find(eg[i].first);
		int b = bs.find(eg[i].second);
		if(a != b) {
			ha[a].insert(b);
			ha[b].insert(a);
		}
	}
	int luf = 0;
	for(int i=0;i<n;i++) {
		if(ha[i].size() == 1) {luf++;}
	}
	int res = (luf+1)/2;
	cout << res << '\n';
}

Compilation message (stderr)

mergers.cpp: In constructor 'U::U(const vi&)':
mergers.cpp:15:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |    for(int i=0;i<w.size();i++) {
      |                ~^~~~~~~~~
mergers.cpp: In function 'void dfa(int, int, int, vi&)':
mergers.cpp:52:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |  for(int i=0;i<g[u].size();i++) {
      |              ~^~~~~~~~~~~~
mergers.cpp: In function 'void proc()':
mergers.cpp:61:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |   for(int i=0;i<g.size();i++) {
      |               ~^~~~~~~~~
mergers.cpp: In function 'int main()':
mergers.cpp:107:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |   for(int j=0;j<bob[i].size();j++) {
      |               ~^~~~~~~~~~~~~~
mergers.cpp:124:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  124 |  for(int i=0;i<eg.size();i++) {
      |              ~^~~~~~~~~~

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