답안 #376834

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
376834	2021-03-12T05:11:44 Z	Kevin_Zhang_TW	Mergers (JOI19_mergers)	C++17	10 / 100	208 ms	46572 KB

mergers

#include <bits/stdc++.h>
using namespace std;
using ll = long long ;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template<class T> void debug(T l, T r) { while (l != r) cerr << *l << " \n"[next(l) == r], ++l; }
#else
#define DE(...) 0
#define debug(...) 0
#endif
const int MAX_N = 500010, MAX_K = 20;

int n, k, belong[MAX_N];
vector<int> edge[MAX_N];
vector<int> state[MAX_N];
ll sum[MAX_N];

int anc[MAX_K][MAX_N], in[MAX_N], out[MAX_N];
bool isanc(int a, int b) { return in[a] <= in[b] && out[a] >= out[b]; }
void dfs(int x, int lst = 1) {
	static int t;
	anc[0][x] = lst;
	in[x] = ++t;
	for (int u : edge[x]) if (u != lst)
		dfs(u, x);
	out[x] = t;
}
void dfs2(int x, int lst = -1) {
	for (int u : edge[x]) if (u != lst) {
		dfs2(u, x);
		sum[x] += sum[u];
	}
}

int dp[MAX_N];

int dfs3(int x, int lst = -1) {
	int son = 0;
	for (int u : edge[x]) if (u != lst)
		son += dfs3(u, x);

	if (son == 0 && sum[x] == 0 && lst != -1) {
		++son;
		DE(x);
	}

	if (lst == -1) {
		int pt = 0, at = 0;
		for (int u : edge[x]) {
			if (sum[u] == 0) {
				++pt;
			}
			if (dp[u] == 0) {
				++at;
			}
		}
		if (pt == 1 && pt + at == edge[x].size())
			++son;

	}
	return dp[x] = son;
}
int getlca(int a, int b) {
	for (int d = MAX_K-1;d >= 0;--d)
		if (!isanc(anc[d][a], b))
			a = anc[d][a];
	return isanc(a, b) ? a : anc[0][a];
}

int32_t main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	cin >> n >> k;
	for (int a, b, i = 1;i < n;++i) {
		cin >> a >> b;
		edge[a].pb(b), edge[b].pb(a);
	}
	for (int i = 1;i <= n;++i) {
		cin >> belong[i];
		state[ belong[i] ].pb(i);
	}
	int rt = 1;

	if (k == 1) return cout << 0 << '\n', 0;


	dfs(rt);
	for (int d = 1;d < MAX_K;++d)
		for (int i = 1;i <= n;++i)
			anc[d][i] = anc[d-1][ anc[d-1][i] ];

	for (int i = 1;i <= k;++i) {
		if (state[i].size() > 1) {
			sort(AI(state[i]), [&](int a, int b) {
					return in[a] < in[b];
					});
			for (int x : state[i])
				++sum[x];
			sum[ getlca(state[i][0], state[i].back()) ] -= state[i].size();
		}
	}

	dfs2(rt);

	int res = dfs3(rt);
	res = (res+1) / 2;
	cout << res << '\n';
}

Compilation message

mergers.cpp: In function 'int dfs3(int, int)':
mergers.cpp:14:17: warning: statement has no effect [-Wunused-value]
   14 | #define DE(...) 0
      |                 ^
mergers.cpp:50:3: note: in expansion of macro 'DE'
   50 |   DE(x);
      |   ^~
mergers.cpp:63:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |   if (pt == 1 && pt + at == edge[x].size())
      |                  ~~~~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	18 ms	24044 KB	Output is correct
2	Correct	17 ms	24044 KB	Output is correct
3	Correct	17 ms	24044 KB	Output is correct
4	Correct	17 ms	24044 KB	Output is correct
5	Correct	17 ms	24044 KB	Output is correct
6	Correct	17 ms	23916 KB	Output is correct
7	Correct	17 ms	23788 KB	Output is correct
8	Correct	17 ms	24044 KB	Output is correct
9	Correct	17 ms	24044 KB	Output is correct
10	Correct	17 ms	24044 KB	Output is correct
11	Correct	17 ms	24044 KB	Output is correct
12	Correct	17 ms	24044 KB	Output is correct
13	Correct	17 ms	24044 KB	Output is correct
14	Correct	17 ms	24044 KB	Output is correct
15	Correct	17 ms	24044 KB	Output is correct
16	Correct	17 ms	24044 KB	Output is correct
17	Correct	17 ms	24044 KB	Output is correct
18	Correct	17 ms	24044 KB	Output is correct
19	Correct	18 ms	24044 KB	Output is correct
20	Correct	17 ms	24044 KB	Output is correct
21	Correct	16 ms	24044 KB	Output is correct
22	Correct	18 ms	24044 KB	Output is correct
23	Correct	17 ms	24044 KB	Output is correct
24	Correct	18 ms	24044 KB	Output is correct

Subtask #2
0 / 24.0

#	결과	실행 시간	메모리	Grader output
1	Correct	18 ms	24044 KB	Output is correct
2	Correct	17 ms	24044 KB	Output is correct
3	Correct	17 ms	24044 KB	Output is correct
4	Correct	17 ms	24044 KB	Output is correct
5	Correct	17 ms	24044 KB	Output is correct
6	Correct	17 ms	23916 KB	Output is correct
7	Correct	17 ms	23788 KB	Output is correct
8	Correct	17 ms	24044 KB	Output is correct
9	Correct	17 ms	24044 KB	Output is correct
10	Correct	17 ms	24044 KB	Output is correct
11	Correct	17 ms	24044 KB	Output is correct
12	Correct	17 ms	24044 KB	Output is correct
13	Correct	17 ms	24044 KB	Output is correct
14	Correct	17 ms	24044 KB	Output is correct
15	Correct	17 ms	24044 KB	Output is correct
16	Correct	17 ms	24044 KB	Output is correct
17	Correct	17 ms	24044 KB	Output is correct
18	Correct	17 ms	24044 KB	Output is correct
19	Correct	18 ms	24044 KB	Output is correct
20	Correct	17 ms	24044 KB	Output is correct
21	Correct	16 ms	24044 KB	Output is correct
22	Correct	18 ms	24044 KB	Output is correct
23	Correct	17 ms	24044 KB	Output is correct
24	Correct	18 ms	24044 KB	Output is correct
25	Correct	17 ms	24044 KB	Output is correct
26	Correct	19 ms	24556 KB	Output is correct
27	Correct	19 ms	24428 KB	Output is correct
28	Correct	19 ms	24684 KB	Output is correct
29	Correct	19 ms	24556 KB	Output is correct
30	Correct	19 ms	24428 KB	Output is correct
31	Correct	19 ms	24044 KB	Output is correct
32	Correct	19 ms	24684 KB	Output is correct
33	Correct	17 ms	24044 KB	Output is correct
34	Correct	19 ms	24556 KB	Output is correct
35	Correct	19 ms	24556 KB	Output is correct
36	Incorrect	19 ms	24428 KB	Output isn't correct
37	Halted	0 ms	0 KB	-

Subtask #3
0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	18 ms	24044 KB	Output is correct
2	Correct	17 ms	24044 KB	Output is correct
3	Correct	17 ms	24044 KB	Output is correct
4	Correct	17 ms	24044 KB	Output is correct
5	Correct	17 ms	24044 KB	Output is correct
6	Correct	17 ms	23916 KB	Output is correct
7	Correct	17 ms	23788 KB	Output is correct
8	Correct	17 ms	24044 KB	Output is correct
9	Correct	17 ms	24044 KB	Output is correct
10	Correct	17 ms	24044 KB	Output is correct
11	Correct	17 ms	24044 KB	Output is correct
12	Correct	17 ms	24044 KB	Output is correct
13	Correct	17 ms	24044 KB	Output is correct
14	Correct	17 ms	24044 KB	Output is correct
15	Correct	17 ms	24044 KB	Output is correct
16	Correct	17 ms	24044 KB	Output is correct
17	Correct	17 ms	24044 KB	Output is correct
18	Correct	17 ms	24044 KB	Output is correct
19	Correct	18 ms	24044 KB	Output is correct
20	Correct	17 ms	24044 KB	Output is correct
21	Correct	16 ms	24044 KB	Output is correct
22	Correct	18 ms	24044 KB	Output is correct
23	Correct	17 ms	24044 KB	Output is correct
24	Correct	18 ms	24044 KB	Output is correct
25	Correct	18 ms	24044 KB	Output is correct
26	Correct	84 ms	39852 KB	Output is correct
27	Correct	120 ms	39404 KB	Output is correct
28	Correct	22 ms	24428 KB	Output is correct
29	Correct	17 ms	24044 KB	Output is correct
30	Correct	19 ms	24044 KB	Output is correct
31	Correct	118 ms	39532 KB	Output is correct
32	Correct	18 ms	24428 KB	Output is correct
33	Correct	156 ms	46572 KB	Output is correct
34	Correct	129 ms	39404 KB	Output is correct
35	Incorrect	19 ms	24428 KB	Output isn't correct
36	Halted	0 ms	0 KB	-

Subtask #4
0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	81 ms	38244 KB	Output is correct
2	Correct	89 ms	40036 KB	Output is correct
3	Correct	19 ms	24428 KB	Output is correct
4	Correct	23 ms	24428 KB	Output is correct
5	Correct	18 ms	24044 KB	Output is correct
6	Correct	17 ms	24044 KB	Output is correct
7	Correct	18 ms	24428 KB	Output is correct
8	Correct	208 ms	40796 KB	Output is correct
9	Incorrect	19 ms	24428 KB	Output isn't correct
10	Halted	0 ms	0 KB	-

Subtask #5
0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	18 ms	24044 KB	Output is correct
2	Correct	17 ms	24044 KB	Output is correct
3	Correct	17 ms	24044 KB	Output is correct
4	Correct	17 ms	24044 KB	Output is correct
5	Correct	17 ms	24044 KB	Output is correct
6	Correct	17 ms	23916 KB	Output is correct
7	Correct	17 ms	23788 KB	Output is correct
8	Correct	17 ms	24044 KB	Output is correct
9	Correct	17 ms	24044 KB	Output is correct
10	Correct	17 ms	24044 KB	Output is correct
11	Correct	17 ms	24044 KB	Output is correct
12	Correct	17 ms	24044 KB	Output is correct
13	Correct	17 ms	24044 KB	Output is correct
14	Correct	17 ms	24044 KB	Output is correct
15	Correct	17 ms	24044 KB	Output is correct
16	Correct	17 ms	24044 KB	Output is correct
17	Correct	17 ms	24044 KB	Output is correct
18	Correct	17 ms	24044 KB	Output is correct
19	Correct	18 ms	24044 KB	Output is correct
20	Correct	17 ms	24044 KB	Output is correct
21	Correct	16 ms	24044 KB	Output is correct
22	Correct	18 ms	24044 KB	Output is correct
23	Correct	17 ms	24044 KB	Output is correct
24	Correct	18 ms	24044 KB	Output is correct
25	Correct	17 ms	24044 KB	Output is correct
26	Correct	19 ms	24556 KB	Output is correct
27	Correct	19 ms	24428 KB	Output is correct
28	Correct	19 ms	24684 KB	Output is correct
29	Correct	19 ms	24556 KB	Output is correct
30	Correct	19 ms	24428 KB	Output is correct
31	Correct	19 ms	24044 KB	Output is correct
32	Correct	19 ms	24684 KB	Output is correct
33	Correct	17 ms	24044 KB	Output is correct
34	Correct	19 ms	24556 KB	Output is correct
35	Correct	19 ms	24556 KB	Output is correct
36	Incorrect	19 ms	24428 KB	Output isn't correct
37	Halted	0 ms	0 KB	-

답안 #376834

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 0 / 24.0

Subtask #3 0 / 14.0

Subtask #4 0 / 22.0

Subtask #5 0 / 30.0

Subtask #1
10.0 / 10.0

Subtask #2
0 / 24.0

Subtask #3
0 / 14.0

Subtask #4
0 / 22.0

Subtask #5
0 / 30.0