oj.uz

Submission #667960

# Submission time Handle Problem Language Result Execution time Memory
667960 2022-12-02T12:18:01 Z dozer Star Trek (CEOI20_startrek) C++14
23 / 100
 1000 ms 39728 KB 
#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++;
	dfs(0, 0, 1, 0);
	dfs(0, 0, 1, 1);
	for (int i = 1; i <= n; i++) if (reach[1][i]) agn++;
	for (int i = 1; i <= n; i++) if (reach[0][i]) gab++;
		
	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";
}

Compilation message

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

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 4308 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 4180 KB Output is correct
4 Correct 2 ms 4180 KB Output is correct
5 Correct 3 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 4180 KB Output is correct
4 Correct 2 ms 4180 KB Output is correct
5 Correct 3 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 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 4180 KB Output is correct
4 Correct 2 ms 4180 KB Output is correct
5 Correct 3 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 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 109 ms 23208 KB Output is correct
13 Correct 136 ms 39728 KB Output is correct
14 Execution timed out 1090 ms 8564 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 4180 KB Output is correct
4 Correct 2 ms 4180 KB Output is correct
5 Correct 3 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 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 3 ms 4180 KB Output is correct
13 Incorrect 3 ms 4192 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 4180 KB Output is correct
4 Correct 2 ms 4180 KB Output is correct
5 Correct 3 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 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 109 ms 23208 KB Output is correct
13 Correct 136 ms 39728 KB Output is correct
14 Execution timed out 1090 ms 8564 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 4308 KB Output isn't correct
3 Halted 0 ms 0 KB -