Submission #668112

#	Time	Username	Problem	Language	Result	Execution time	Memory
668112		dozer	Star Trek (CEOI20_startrek)	C++14	38 / 100	71 ms	17764 KiB

startrek

#include <bits/stdc++.h>
using namespace std;
#define fastio() cin.tie(0), ios_base::sync_with_stdio(0)
#define fileio() freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout)
#define pb push_back
#define pii pair<int, int>
#define st first
#define nd second
#define sp " "
#define endl "\n"
#define modulo 1000000007
#define N 100005
#define int long long

int ans[N], dp[N], cnt[N], c[N];
vector<int> adj[N];

void dfs(int node, int root)
{
	dp[node] = 0;
	for (auto i : adj[node])
	{
		if (i == root) continue;
		dfs(i, node);
		if (dp[i] == 0) cnt[node]++, dp[node] = 1;
	}
	ans[node] = dp[node];
}

void reroot(int node, int root)
{
	for (auto i : adj[node])
	{
		if (i == root) continue;
		int curr = ans[node];
		if (cnt[node]== 1 && ans[i] == 0) curr = 0;
		if (curr == 0) cnt[i]++;
		if (cnt[i]) ans[i] = 1;
		reroot(i, node); 
	}
}

void critical(int node, int root)
{
	if (dp[node] == 0) c[node] = 1;
	if (dp[node] == 0)
	{
		for (auto i : adj[node])
		{
			if (i == root) continue;
			critical(i, node);
			if (dp[i] == 1) c[node] += c[i];
		}
	}
	else
	{
		int cntr = 0;
		for (auto i : adj[node])
		{
			if (i == root) continue;
			critical(i, node);
			if (dp[i] == 0) cntr++;
		}
		if (cntr == 1)
		{
			for (auto i : adj[node])
			{
				if (i == root) continue;
				if (dp[i] == 0) c[node] += c[i];
			}
		}
	}
}


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

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

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


	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);
	}

	dfs(1, 0);
	
	reroot(1, 0);
	critical(1, 0);
	
	int sum = 0;
	for (int i = 1; i <= n; i++) if (ans[i] == 0) sum++;
	int res;
	if (ans[1] == 0)
	{
		res = mul(sum, c[1]);
	}
	else
	{
		res = mul(n, n);
		res = subs(res, mul(sum, c[1]));
	}

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

• Subtask 1: 0 / 0
• Subtask 2: 0 / 7
• Subtask 3: 8 / 8
• Subtask 4: 15 / 15
• Subtask 5: 15 / 15
• Subtask 6: 0 / 20
• Subtask 7: 0 / 20
• Subtask 8: 0 / 15