oj.uz

Submission #667958

# Submission time Handle Problem Language Result Execution time Memory
667958 2022-12-02T12:15:58 Z dozer Star Trek (CEOI20_startrek) C++14
23 / 100
 1000 ms 39860 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 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);

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++;
		//cout<<res<<sp<<sum<<endl;
	dfs(0, 0, 1, 0);
	dfs(0, 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 3 ms 4180 KB Output is correct
2 Incorrect 4 ms 4180 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

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

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4180 KB Output is correct
2 Correct 2 ms 4180 KB Output is correct
3 Correct 2 ms 4248 KB Output is correct
4 Correct 3 ms 4180 KB Output is correct
5 Correct 2 ms 4180 KB Output is correct
6 Correct 2 ms 4180 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4180 KB Output is correct
2 Correct 2 ms 4180 KB Output is correct
3 Correct 2 ms 4248 KB Output is correct
4 Correct 3 ms 4180 KB Output is correct
5 Correct 2 ms 4180 KB Output is correct
6 Correct 2 ms 4180 KB Output is correct
7 Correct 3 ms 4308 KB Output is correct
8 Correct 2 ms 4564 KB Output is correct
9 Correct 4 ms 4180 KB Output is correct
10 Correct 3 ms 4308 KB Output is correct
11 Correct 3 ms 4308 KB Output is correct

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4180 KB Output is correct
2 Correct 2 ms 4180 KB Output is correct
3 Correct 2 ms 4248 KB Output is correct
4 Correct 3 ms 4180 KB Output is correct
5 Correct 2 ms 4180 KB Output is correct
6 Correct 2 ms 4180 KB Output is correct
7 Correct 3 ms 4308 KB Output is correct
8 Correct 2 ms 4564 KB Output is correct
9 Correct 4 ms 4180 KB Output is correct
10 Correct 3 ms 4308 KB Output is correct
11 Correct 3 ms 4308 KB Output is correct
12 Correct 117 ms 23212 KB Output is correct
13 Correct 143 ms 39860 KB Output is correct
14 Execution timed out 1092 ms 8480 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4180 KB Output is correct
2 Correct 2 ms 4180 KB Output is correct
3 Correct 2 ms 4248 KB Output is correct
4 Correct 3 ms 4180 KB Output is correct
5 Correct 2 ms 4180 KB Output is correct
6 Correct 2 ms 4180 KB Output is correct
7 Correct 3 ms 4308 KB Output is correct
8 Correct 2 ms 4564 KB Output is correct
9 Correct 4 ms 4180 KB Output is correct
10 Correct 3 ms 4308 KB Output is correct
11 Correct 3 ms 4308 KB Output is correct
12 Correct 2 ms 4180 KB Output is correct
13 Incorrect 2 ms 4180 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4180 KB Output is correct
2 Correct 2 ms 4180 KB Output is correct
3 Correct 2 ms 4248 KB Output is correct
4 Correct 3 ms 4180 KB Output is correct
5 Correct 2 ms 4180 KB Output is correct
6 Correct 2 ms 4180 KB Output is correct
7 Correct 3 ms 4308 KB Output is correct
8 Correct 2 ms 4564 KB Output is correct
9 Correct 4 ms 4180 KB Output is correct
10 Correct 3 ms 4308 KB Output is correct
11 Correct 3 ms 4308 KB Output is correct
12 Correct 117 ms 23212 KB Output is correct
13 Correct 143 ms 39860 KB Output is correct
14 Execution timed out 1092 ms 8480 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #8
0 / 15.0

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