제출 #667935

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
667935		dozer	Star Trek (CEOI20_startrek)	C++14	0 / 100	9 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];

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
• 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