oj.uz

Submission #882078

# Submission time Handle Problem Language Result Execution time Memory
882078 2023-12-02T14:45:13 Z vjudge1 Star Trek (CEOI20_startrek) C++17
38 / 100
 52 ms 17252 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 != 0);
	c = (u == 0)? 0 : !dp[u];
	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);
		dp[0] = 1;
		dfs2(0, 0, 2);
		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 3164 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 2912 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4956 KB Output is correct
2 Correct 1 ms 4956 KB Output is correct
3 Correct 1 ms 4956 KB Output is correct
4 Correct 1 ms 4956 KB Output is correct
5 Correct 2 ms 4956 KB Output is correct
6 Correct 1 ms 4956 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4956 KB Output is correct
2 Correct 1 ms 4956 KB Output is correct
3 Correct 1 ms 4956 KB Output is correct
4 Correct 1 ms 4956 KB Output is correct
5 Correct 2 ms 4956 KB Output is correct
6 Correct 1 ms 4956 KB Output is correct
7 Correct 1 ms 5212 KB Output is correct
8 Correct 1 ms 5184 KB Output is correct
9 Correct 1 ms 5212 KB Output is correct
10 Correct 1 ms 5212 KB Output is correct
11 Correct 1 ms 5212 KB Output is correct

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4956 KB Output is correct
2 Correct 1 ms 4956 KB Output is correct
3 Correct 1 ms 4956 KB Output is correct
4 Correct 1 ms 4956 KB Output is correct
5 Correct 2 ms 4956 KB Output is correct
6 Correct 1 ms 4956 KB Output is correct
7 Correct 1 ms 5212 KB Output is correct
8 Correct 1 ms 5184 KB Output is correct
9 Correct 1 ms 5212 KB Output is correct
10 Correct 1 ms 5212 KB Output is correct
11 Correct 1 ms 5212 KB Output is correct
12 Correct 47 ms 13136 KB Output is correct
13 Correct 52 ms 17252 KB Output is correct
14 Correct 25 ms 9808 KB Output is correct
15 Correct 46 ms 9944 KB Output is correct
16 Correct 36 ms 10072 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4956 KB Output is correct
2 Correct 1 ms 4956 KB Output is correct
3 Correct 1 ms 4956 KB Output is correct
4 Correct 1 ms 4956 KB Output is correct
5 Correct 2 ms 4956 KB Output is correct
6 Correct 1 ms 4956 KB Output is correct
7 Correct 1 ms 5212 KB Output is correct
8 Correct 1 ms 5184 KB Output is correct
9 Correct 1 ms 5212 KB Output is correct
10 Correct 1 ms 5212 KB Output is correct
11 Correct 1 ms 5212 KB Output is correct
12 Correct 1 ms 5176 KB Output is correct
13 Incorrect 1 ms 3136 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4956 KB Output is correct
2 Correct 1 ms 4956 KB Output is correct
3 Correct 1 ms 4956 KB Output is correct
4 Correct 1 ms 4956 KB Output is correct
5 Correct 2 ms 4956 KB Output is correct
6 Correct 1 ms 4956 KB Output is correct
7 Correct 1 ms 5212 KB Output is correct
8 Correct 1 ms 5184 KB Output is correct
9 Correct 1 ms 5212 KB Output is correct
10 Correct 1 ms 5212 KB Output is correct
11 Correct 1 ms 5212 KB Output is correct
12 Correct 47 ms 13136 KB Output is correct
13 Correct 52 ms 17252 KB Output is correct
14 Correct 25 ms 9808 KB Output is correct
15 Correct 46 ms 9944 KB Output is correct
16 Correct 36 ms 10072 KB Output is correct
17 Correct 1 ms 5176 KB Output is correct
18 Incorrect 1 ms 3136 KB Output isn't correct
19 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 3164 KB Output isn't correct
3 Halted 0 ms 0 KB -