Submission #667961

#	Time	Username	Problem	Language	Result	Execution time	Memory
667961		dozer	Star Trek (CEOI20_startrek)	C++14	23 / 100	1070 ms	39848 KiB

startrek

#pragma once
#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 100005
#define ll long long

const int modulo = 1e9 + 7;

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

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

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

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

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

inline void dfs(int ind, int j, int dep, int turn)
{
	int node = edge[ind][j];
	int root = edge[ind][1 - j];
	int player = dep % 2;
	if (player == turn) reach[turn][node] = 1;
	int cnt = 0;
	for (auto i : adj[node])
	{
		int curr = edge[i.st][i.nd];
		if (curr == root) continue;
		if (f(i.st, i.nd, 1 - player) == 1 - turn) cnt++;
	}
	if (player == turn || cnt == 1)
	{
		for (auto i : adj[node])
		{
			int curr = edge[i.st][i.nd];
			if (curr == root) continue;
			if (turn != player && f(i.st, i.nd, 1 - player) != player) continue;
			dfs(i.st, i.nd, dep + 1, turn);
		}
	}
}

inline int gh(int node, int turn)
{
	int ans = 0;
	if (turn == 0) ans = 1;
	for (auto i : adj[node])
	{
		if (turn == 0) ans &= f(i.st, i.nd, 1 - turn);
		else ans |= f(i.st, i.nd, 1 - turn);
	}
	return ans;
}

inline int f(int ind, int j, int turn)
{
	if(dp[ind][j][turn] != -1) return dp[ind][j][turn];
	int ans = 0;
	if (turn == 0) ans = 1;
	for (auto i : adj[edge[ind][j]])
	{
		if (i.st == ind) continue;
		if (turn == 0) ans &= f(i.st, i.nd, 1 - turn);
		else ans |= f(i.st, i.nd, 1 - turn);
	}
	return dp[ind][j][turn] = ans;
}


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


	memset(dp, -1, sizeof(dp));
	int n, d;
	cin>>n>>d;
	edge[0][0] = 1;
	for (int i = 1; i < n; i++)
	{
		int u, v;
		cin>>u>>v;
		adj[u].pb({i, 0});
		adj[v].pb({i, 1});

		edge[i][0] = v;
		edge[i][1] = u;
	}
	
	int res = gh(1, 1);
	int sum = 0;
	int agn = 0, gab = 0;
	for (int i = 1; i <= n; i++) if (gh(i, 0)) sum++;

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

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

Compilation message (stderr)

startrek.cpp:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

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