oj.uz

Submission #881491

# Submission time Handle Problem Language Result Execution time Memory
881491 2023-12-01T09:57:06 Z vjudge1 Star Trek (CEOI20_startrek) C++17
0 / 100
 1 ms 4956 KB 
// In the Name of Allah

#include<bits/stdc++.h>
using namespace std;

#define int long long
#define F first
#define S second
#define pii pair<int, int>
#define pb push_back
#define pp pop_back
#define all(x) x.begin(), x.end()
#define unq(x) sort(all(x)), x.resize(unique(all(x)) - x.begin())

const int N = 1e5 + 12, mod = 1'000'000'000 + 7;
vector<int> g[N];
int n, d, k[2], sz[N];
bool dpd[N], dp[N];
pii res[N];

void ip() {
	cin >> n >> d;
	for (int i = 1; i < n; i++) {
		int u, v;
		cin >> u >> v;
		u--, v--;
		g[u].pb(v);
		g[v].pb(u);
	}
}

void dfs1(int u, int par) {
	sz[u] = 1;
	for (auto i: g[u])
		if (i != par) {
			dfs1(i, u);
			dpd[u] |= dpd[i];
			sz[u] += sz[i];
		}
	dpd[u] = !dpd[u];
}

void dfs2(int u, int par, int c) {
	c -= !dpd[u];
	dp[u] = !c;
	if (u)
		c = !dp[par];
	else if (g[u].size() == 1)
		c = 1;
	else
		c = 0;
	for (auto i: g[u])
		if (i != par)
			c += !dpd[i];
	for (auto i: g[u])
		if (i != par)
			dfs2(i, u, c);
}

void dfs3(int u, int par) {
	int c = 0, v = 0;
	for (auto i: g[u])
		if (i != par) {
			dfs3(i, u);
			c += dpd[i];
			if (dpd[i])
				v = i;
		}
	if (!c) {
		for (auto i: g[u])
			if (i != par) {
				res[u].F += res[i].S;
				res[u].S += res[i].F;
			}
		res[u].F += k[1];
		res[u].S += k[0];
	}
	else if (c == 1) {
		res[u].F = (sz[u] - sz[v]) * n + res[v].S;
		res[u].S = res[v].F;
	}
	else 
		res[u].F = sz[u] * n;
}

void solve() {
	if (d == 1) {
		dfs1(0, 0);
		dfs2(0, 0, !dpd[0]);
		for (int i = 0; i < n; i++) {
			dp[i] &= dpd[i];
			k[dp[i]]++;
		}
		dfs3(0, 0);
		cout << res[0].F % mod;
	}
}

int32_t main() {
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	ip(), solve();
	return 0;
}

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4956 KB Output is correct
2 Incorrect 1 ms 3124 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2904 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4952 KB Output is correct
2 Incorrect 1 ms 4952 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4952 KB Output is correct
2 Incorrect 1 ms 4952 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4952 KB Output is correct
2 Incorrect 1 ms 4952 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4952 KB Output is correct
2 Incorrect 1 ms 4952 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4952 KB Output is correct
2 Incorrect 1 ms 4952 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4956 KB Output is correct
2 Incorrect 1 ms 3124 KB Output isn't correct
3 Halted 0 ms 0 KB -