oj.uz

Submission #667957

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

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

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;
}
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 2 ms 4180 KB Output is correct
2 Incorrect 3 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 2 ms 4180 KB Output is correct
2 Correct 3 ms 4180 KB Output is correct
3 Correct 2 ms 4180 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 3 ms 4180 KB Output is correct
3 Correct 2 ms 4180 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 2 ms 4308 KB Output is correct
8 Correct 3 ms 4308 KB Output is correct
9 Correct 3 ms 4180 KB Output is correct
10 Correct 2 ms 4180 KB Output is correct
11 Correct 2 ms 4180 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 3 ms 4180 KB Output is correct
3 Correct 2 ms 4180 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 2 ms 4308 KB Output is correct
8 Correct 3 ms 4308 KB Output is correct
9 Correct 3 ms 4180 KB Output is correct
10 Correct 2 ms 4180 KB Output is correct
11 Correct 2 ms 4180 KB Output is correct
12 Correct 117 ms 13528 KB Output is correct
13 Correct 127 ms 19064 KB Output is correct
14 Execution timed out 1078 ms 9484 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 3 ms 4180 KB Output is correct
3 Correct 2 ms 4180 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 2 ms 4308 KB Output is correct
8 Correct 3 ms 4308 KB Output is correct
9 Correct 3 ms 4180 KB Output is correct
10 Correct 2 ms 4180 KB Output is correct
11 Correct 2 ms 4180 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 2 ms 4180 KB Output is correct
2 Correct 3 ms 4180 KB Output is correct
3 Correct 2 ms 4180 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 2 ms 4308 KB Output is correct
8 Correct 3 ms 4308 KB Output is correct
9 Correct 3 ms 4180 KB Output is correct
10 Correct 2 ms 4180 KB Output is correct
11 Correct 2 ms 4180 KB Output is correct
12 Correct 117 ms 13528 KB Output is correct
13 Correct 127 ms 19064 KB Output is correct
14 Execution timed out 1078 ms 9484 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 3 ms 4180 KB Output isn't correct
3 Halted 0 ms 0 KB -