oj.uz

Submission #881478

# Submission time Handle Problem Language Result Execution time Memory
881478 2023-12-01T09:33:15 Z vjudge1 Star Trek (CEOI20_startrek) C++17
0 / 100
 3 ms 4204 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, c[2];
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) {
	for (auto i: g[u])
		if (i != par) {
			dfs1(i, u);
			dpd[u] |= dpd[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) {
	if (dpd[u]) {
		res[u].F += c[1];
		res[u].S += c[0];
	}
	else 
		res[u].F += n;
	for (auto i: g[u])
		if (i != par) {
			dfs3(i, u);
			res[u].F += res[i].S;
			res[u].S += res[i].F;
		}
}

void solve() {
	if (d == 1) {
		dfs1(0, 0);
		dfs2(0, 0, !dpd[0]);
		for (int i = 0; i < n; i++) {
			dp[i] &= dpd[i];
			c[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 4188 KB Output is correct
2 Incorrect 3 ms 4204 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 4188 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 4188 KB Output is correct
2 Incorrect 2 ms 4184 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 4188 KB Output is correct
2 Incorrect 2 ms 4184 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 4188 KB Output is correct
2 Incorrect 2 ms 4184 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 4188 KB Output is correct
2 Incorrect 2 ms 4184 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 4188 KB Output is correct
2 Incorrect 2 ms 4184 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 4188 KB Output is correct
2 Incorrect 3 ms 4204 KB Output isn't correct
3 Halted 0 ms 0 KB -