Submission #667921

#	Time	Username	Problem	Language	Result	Execution time	Memory
667921		dozer	Star Trek (CEOI20_startrek)	C++14	0 / 100	8 ms	16160 KiB

startrek

#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];

void dfs(int node, int root, int dep, int turn)
{
	if (dep % 2 == turn) reach[turn][node] = 1;
	//cout<<node<<sp<<turn<<sp<<reach[turn][node]<<endl;
	if (root == 0 && adj[node].size() != 1) return;
	if (root != 0 && adj[node].size() != 2) return;
	for (auto i : adj[node])
	{
		if (i == root) continue;
		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);
	}
	//cout<<node<<sp<<root<<sp<<turn<<" : "<<ans<<endl;
	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;
	dfs(1, 0, 1, 0);
	dfs(1, 0, 1, 1);
	for (int i = 1; i <= n; i++) if (f(i, 0, 0)) sum++;
	for (int i = 1; i <= n; i++) if (reach[1][i]) agn++;
	for (int i = 1; i <= n; i++) if (reach[0][i]) gab++;
	int ans = 0;
	//cout<<res<<endl;
	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
• Subtask 2: 0 / 7
• Subtask 3: 0 / 8
• Subtask 4: 0 / 15
• Subtask 5: 0 / 15
• Subtask 6: 0 / 20
• Subtask 7: 0 / 20
• Subtask 8: 0 / 15