oj.uz

Submission #667935

# Submission time Handle Problem Language Result Execution time Memory
667935 2022-12-02T11:50:23 Z dozer Star Trek (CEOI20_startrek) C++14
0 / 100
 9 ms 16160 KB 
#include <bits/stdc++.h>
using namespace std;
#define fileio() freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout)
#define fastio() cin.tie(0), ios_base::sync_with_stdio(0)
#define sp " "
//#define endl "\n"
#define pb push_back
#define pii pair<int, int>
#define st first
#define nd second
#define N 1005
#define int long long

const int modulo = 1e9 + 7;

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

int add(int a, int b)
{
	if (a + b < modulo) return a + b;
	return a + b - modulo;
}

int subs(int a, int b)
{
	if (a < b) return a - b + modulo;
	return a - b;
}

int dp[N][N][2], reach[2][N];
vector<int> adj[N];

int f(int node, int root, int turn);

void dfs(int node, int root, int dep, int turn)
{
	int player = dep % 2;
	if (player == turn) reach[turn][node] = 1;
	int cnt = 0;
	for (auto i : adj[node])
	{
		if (i == root) continue;
		if (f(i, node, 1 - player) == 1 - turn) cnt++;
	}
	if (cnt == 1)
	{
		for (auto i : adj[node])
		{
			if (i == root) continue;
			if (f(i, node, 1 - player) == 1 - turn) dfs(i, node, dep + 1, turn);
		}
	}
}

int f(int node, int root, int turn)
{
	if(dp[node][root][turn] != -1) return dp[node][root][turn];
	int ans = 0;
	if (turn == 0) ans = 1;
	for (auto i : adj[node])
	{
		if (i == root) continue;
		if (turn == 0) ans &= f(i, node, 1 - turn);
		else ans |= f(i, node, 1 - turn);
	}
	return dp[node][root][turn] = ans;
}


int32_t main()
{
	#ifndef ONLINE_JUDGE
	//fileio();
	#endif
	fastio();


	memset(dp, -1, sizeof(dp));
	int n, d;
	cin>>n>>d;
	for (int i = 1; i < n; i++)
	{
		int u, v;
		cin>>u>>v;
		adj[u].pb(v);
		adj[v].pb(u);
	}
	
	int res = f(1, 0, 1);
	int sum = 0;
	int agn = 0, gab = 0;
	for (int i = 1; i <= n; i++) if (f(i, 0, 0)) sum++;
	dfs(1, 0, 1, 0);
	dfs(1, 0, 1, 1);
	for (int i = 1; i <= n; i++) if (reach[1][i]) agn++;
		//cout<<endl;
	for (int i = 1; i <= n; i++) if (reach[0][i]) gab++;
		//cout<<endl;
	int ans = 0;
	if (res == 1)
	{
		ans = mul(n, n);
		ans = subs(ans, mul(sum, gab));
	}
	else
	{
		ans = mul(agn, sum);
	}

	cout<<ans<<endl;
	cerr<<"time taken : "<<clock() / CLOCKS_PER_SEC<<" seconds\n";
}

Subtask #1
0.0 / 0.0

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

Subtask #2
0 / 7.0

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

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 16084 KB Output is correct
2 Correct 6 ms 16084 KB Output is correct
3 Correct 7 ms 16080 KB Output is correct
4 Incorrect 8 ms 16160 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 16084 KB Output is correct
2 Correct 6 ms 16084 KB Output is correct
3 Correct 7 ms 16080 KB Output is correct
4 Incorrect 8 ms 16160 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 16084 KB Output is correct
2 Correct 6 ms 16084 KB Output is correct
3 Correct 7 ms 16080 KB Output is correct
4 Incorrect 8 ms 16160 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 16084 KB Output is correct
2 Correct 6 ms 16084 KB Output is correct
3 Correct 7 ms 16080 KB Output is correct
4 Incorrect 8 ms 16160 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 16084 KB Output is correct
2 Correct 6 ms 16084 KB Output is correct
3 Correct 7 ms 16080 KB Output is correct
4 Incorrect 8 ms 16160 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #8
0 / 15.0

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