Submission #1216876

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216876		MateiKing80	Star Trek (CEOI20_startrek)	C++20	23 / 100	82 ms	10824 KiB

startrek

#include <bits/stdc++.h>

using namespace std;

const int mod = 1e9 + 7, N = 1e5 + 5;

int mul(int a, int b) {
	return (a * b) % mod;
}

int dif(int a, int b) {
	if (a < b) 
		return a - b + mod;
	return a - b;
}

int dp[N], cnt[N], c[N], ans[N];
vector<int> vec[N];

void dfs(int nod, int rad) {
	dp[nod] = 0;
	for (auto i : vec[nod]) {
		if (i == rad) 
			continue;
		dfs(i, nod);
		if (dp[i] == 0) { 
			cnt[nod] ++;
			dp[nod] = 1;
		}
	}
	ans[nod] = dp[nod];
}

void reroot(int nod, int rad) {
	for (auto i : vec[nod]) {
		if (i == rad) 
			continue;
		int curr = ans[nod];
		if (cnt[nod] == 1 && ans[i] == 0) 
			curr = 0;
		if (curr == 0) 
			cnt[i] ++;
		if (cnt[i]) 
			ans[i] = 1;
		reroot(i, nod); 
	}
}

void decon(int nod, int rad) {
	if (dp[nod] == 0) 
		c[nod] = 1;
	if (dp[nod] == 0) {
		for (auto i : vec[nod]) {
			if (i == rad) continue;
			decon(i, nod);
			if (dp[i] == 1) 
				c[nod] += c[i];
		}
	}
	else {
		int ccnt = 0;
		for (auto i : vec[nod]) {
			if (i == rad) 
				continue;
			decon(i, nod);
			if (dp[i] == 0) 
				ccnt ++;
		}
		if (ccnt == 1) {
			for (auto i : vec[nod]) {
				if (i == rad) 
					continue;
				if (dp[i] == 0) 
					c[nod] += c[i];
			}
		}
	}
}

signed main() {
	int n, d, sum = 0;
	cin >> n >> d;
	for (int i = 1; i < n; i ++) {
		int u, v;
		cin >> u >> v;
		vec[u].push_back(v);
		vec[v].push_back(u);
	}
	dfs(1, 0);
	reroot(1, 0);
	decon(1, 0);
	for (int i = 1; i <= n; i ++) 
		if (ans[i] == 0) 
			sum ++;
	int res;
	if (ans[1] == 0)
		res = mul(sum, c[1]);
	else {
		res = mul(n, n);
		res = dif(res, mul(sum, c[1]));
	}
	cout << res << '\n';
}

• Subtask 1: 0 / 0
• Subtask 2: 0 / 7
• Subtask 3: 8 / 8
• Subtask 4: 15 / 15
• Subtask 5: 0 / 15
• Subtask 6: 0 / 20
• Subtask 7: 0 / 20
• Subtask 8: 0 / 15