oj.uz

Submission #667962

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

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

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4180 KB Output is correct
2 Incorrect 2 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 2 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 3 ms 4180 KB Output is correct
2 Correct 2 ms 4180 KB Output is correct
3 Correct 2 ms 4180 KB Output is correct
4 Correct 2 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 3 ms 4180 KB Output is correct
2 Correct 2 ms 4180 KB Output is correct
3 Correct 2 ms 4180 KB Output is correct
4 Correct 2 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 2 ms 4308 KB Output is correct
8 Correct 3 ms 4504 KB Output is correct
9 Correct 4 ms 4180 KB Output is correct
10 Correct 2 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 3 ms 4180 KB Output is correct
2 Correct 2 ms 4180 KB Output is correct
3 Correct 2 ms 4180 KB Output is correct
4 Correct 2 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 2 ms 4308 KB Output is correct
8 Correct 3 ms 4504 KB Output is correct
9 Correct 4 ms 4180 KB Output is correct
10 Correct 2 ms 4308 KB Output is correct
11 Correct 3 ms 4308 KB Output is correct
12 Correct 110 ms 19240 KB Output is correct
13 Correct 139 ms 39752 KB Output is correct
14 Execution timed out 1085 ms 8528 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4180 KB Output is correct
2 Correct 2 ms 4180 KB Output is correct
3 Correct 2 ms 4180 KB Output is correct
4 Correct 2 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 2 ms 4308 KB Output is correct
8 Correct 3 ms 4504 KB Output is correct
9 Correct 4 ms 4180 KB Output is correct
10 Correct 2 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 3 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 3 ms 4180 KB Output is correct
2 Correct 2 ms 4180 KB Output is correct
3 Correct 2 ms 4180 KB Output is correct
4 Correct 2 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 2 ms 4308 KB Output is correct
8 Correct 3 ms 4504 KB Output is correct
9 Correct 4 ms 4180 KB Output is correct
10 Correct 2 ms 4308 KB Output is correct
11 Correct 3 ms 4308 KB Output is correct
12 Correct 110 ms 19240 KB Output is correct
13 Correct 139 ms 39752 KB Output is correct
14 Execution timed out 1085 ms 8528 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #8
0 / 15.0

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