Submission #497880

#	Time	Username	Problem	Language	Result	Execution time	Memory
497880		maomao90	Mergers (JOI19_mergers)	C++17	100 / 100	1313 ms	161476 KiB

mergers

// She will give birth to a son, and you are to give him the name Jesus,
// because he will save his people from their sins.
// Matthew 1:21
#include <bits/stdc++.h> 
using namespace std;

template <class T>
inline bool mnto(T& a, T b) {return a > b ? a = b, 1 : 0;}
template <class T>
inline bool mxto(T& a, T b) {return a < b ? a = b, 1: 0;}
#define REP(i, s, e) for (int i = s; i < e; i++)
#define RREP(i, s, e) for (int i = s; i >= e; i--)
typedef long long ll;
typedef long double ld;
#define MP make_pair
#define FI first
#define SE second
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
#define MT make_tuple
typedef tuple<int, int, int> iii;
#define ALL(_a) _a.begin(), _a.end()
#define pb push_back
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;

#ifdef DEBUG
#define debug(args...) printf(args)
#else
#define debug(args...)
#endif

#define INF 1000000005
#define LINF 1000000000000000005
#define MOD 1000000007
#define MAXN 500005
#define MAXL 20

int n, k;
vi adj[MAXN], nadj[MAXN];
int s[MAXN];
vi col[MAXN];
bool visited[MAXN];
int ans;

int pre[MAXN], pst[MAXN], l[MAXN], p[MAXL][MAXN], ptr;
void dfs(int u, int cp) {
	pre[u] = ptr++;
	p[0][u] = cp;
	REP (k, 1, MAXL) {
		if (p[k - 1][u] == -1) {
			p[k][u] = -1;
		} else {
			p[k][u] = p[k - 1][p[k - 1][u]];
		}
	}
	for (int v : adj[u]) {
		if (v == cp) continue;
		l[v] = l[u] + 1;
		dfs(v, u);
	}
	pst[u] = ptr;
}
int lca(int a, int b) {
	if (l[a] < l[b]) swap(a, b);
	RREP (k, MAXL - 1, 0) {
		if (p[k][a] == -1) continue;
		if (l[p[k][a]] >= l[b]) {
			a = p[k][a];
		}
	}
	if (a == b) {
		return a;
	}
	RREP (k, MAXL - 1, 0) {
		if (p[k][a] != p[k][b]) {
			a = p[k][a];
			b = p[k][b];
		}
	}
	return p[0][a];
}

int dsup[MAXN], rnk[MAXN], compp[MAXN];
int findp(int a) {
	if (dsup[a] == a) return a;
	return dsup[a] = findp(dsup[a]);
}
bool join(int a, int b) {
	int pa = findp(a), pb = findp(b);
	int np = compp[pb];
	if (pa == pb) return 0;
	if (rnk[pa] < rnk[pb]) swap(pa, pb);
	if (rnk[pa] == rnk[pb]) rnk[pa]++;
	dsup[pb] = pa;
	compp[pa] = np;
	return 1;
}

int main() {
	int _t = 1;
   	//scanf("%d", &_t);
	while (_t--) {
		scanf("%d%d", &n, &k);
		REP (i, 0, n + 1) {
			dsup[i] = i;
		}
		REP (i, 1, n) {
			int a, b; scanf("%d%d", &a, &b);
			adj[a].pb(b);
			adj[b].pb(a);
		}
		REP (i, 1, n + 1) {
			scanf("%d", &s[i]);
			col[s[i]].pb(i);
		}
		dfs(1, -1);
		REP (i, 1, n + 1) {
			compp[i] = p[0][i];
		}
		REP (i, 1, k + 1) {
			if (col[i].size() == 1) continue;
			sort(ALL(col[i]), [&] (int l, int r) {
					return pre[l] < pre[r];
					});
			int lc = col[i][0];
			for (int u : col[i]) {
				lc = lca(lc, u);
			}
			for (int u : col[i]) {
				while (compp[findp(u)] != -1 && l[compp[findp(u)]] >= l[lc]) {
					join(u, compp[findp(u)]);
				}
			}
		}
		int sze = 0;
		REP (u, 1, n + 1) {
			debug("%d: %d\n", u, findp(u));
			for (int v : adj[u]) {
				if (findp(u) == findp(v)) {
					continue;
				}
				nadj[findp(u)].pb(findp(v));
			}
		}
		REP (u, 1, n + 1) {
			if (visited[findp(u)]) continue;
			visited[findp(u)] = 1;
			sze++;
		}
		REP (i, 1, n + 1) {
			if (nadj[i].empty()) continue;
			sort(ALL(nadj[i]));
			nadj[i].erase(unique(ALL(nadj[i])), nadj[i].end());
		}
		REP (i, 1, n + 1) {
			if (nadj[i].size() == 1) {
				ans++;
			}
		}
		printf("%d\n", (ans + 1) / 2);
	}
	return 0;
}

Compilation message (stderr)

mergers.cpp: In function 'int main()':
mergers.cpp:106:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  106 |   scanf("%d%d", &n, &k);
      |   ~~~~~^~~~~~~~~~~~~~~~
mergers.cpp:111:19: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  111 |    int a, b; scanf("%d%d", &a, &b);
      |              ~~~~~^~~~~~~~~~~~~~~~
mergers.cpp:116:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  116 |    scanf("%d", &s[i]);
      |    ~~~~~^~~~~~~~~~~~~

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