Submission #588776

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
588776	2022-07-04T04:34:08 Z	jiahng	Star Trek (CEOI20_startrek)	C++14	23 / 100	1000 ms	20652 KB

startrek

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define int ll
typedef pair<int32_t, int32_t> pi;
typedef vector <int> vi;
typedef vector <pi> vpi;
typedef pair<pi, ll> pii;
typedef set <ll> si;
typedef long double ld;
#define f first
#define s second
#define mp make_pair
#define FOR(i,s,e) for(int i=s;i<=int(e);++i)
#define DEC(i,s,e) for(int i=s;i>=int(e);--i)
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define lbd(x, y) lower_bound(all(x), y)
#define ubd(x, y) upper_bound(all(x), y)
#define aFOR(i,x) for (auto i: x)
#define mem(x,i) memset(x,i,sizeof x)
#define fast ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define maxn 400010
#define INF (ll)(1e9+10)
#define MOD 1000000007
typedef pair <vi, int> pvi;
typedef pair <int,pi> ipi;
typedef vector <pii> vpii;
typedef pair <pi,pi> pipi;

int N,D,a,b;
vi adj[maxn];

bool win[maxn];
int firstpar[maxn], depth[maxn];

void dfs(int x, int p){
	win[x] = 0;
	aFOR(i,adj[x]) if (i != p){
		depth[i] = depth[x] + 1; dfs(i,x);
		win[x] |= !win[i];
	}
}

void dfs2(int x,int p){
	if (p == -1) firstpar[x] = x;
	else{
		firstpar[x] = firstpar[p];
		aFOR(i, adj[p]) if (depth[i] == depth[x] && i != x && !win[i]){
			firstpar[x] = x;
		}
	}
	aFOR(i,adj[x]) if (i != p) dfs2(i,x);
}

int qexp(int a,int b){
	int ans = 1;
	while (b){
		if (b & 1) (ans *= a) %= MOD;
		(a *= a) %= MOD;
		b <<= 1;
	}
	return ans;
}
int32_t main(){
    fast;
    cin >> N >> D;
    FOR(i,1,N-1){
		cin >> a >> b; adj[a].pb(b); adj[b].pb(a);
	}
	
	int numnexte = 0,numnexto = 0, numwin = 0;
	int nnexte1=0,nnexto1=0, nwin1=0;
	
	int ans = 0;
	FOR(i,1,N){
		depth[i] = 0; dfs(i,-1); dfs2(i,-1);
		ans += win[i];
		int nnexte = 0,nnexto = 0, nwin = 0;
		FOR(j,1,N){
			if ((depth[j] - depth[firstpar[j]]) % 2 == 1 || win[j]){
				//~ cout << "NWIN " << j << '\n';
				nwin++;
				if (j == 1) nwin1++;
			}else if (firstpar[j] == i){
				if (depth[j]%2 == 0){
					//~ cout << "NNEXTE " << j << '\n';
					nnexte++;
					if (j == 1) nnexte1++;
				}else{
					nnexto++;
					if (j == 1) nnexto1++;
					//~ cout << "NNEXTO " << j << '\n';
				}
			}
		}
		//~ if (i == 1){
			//~ nnexte1 = nnexte; nnexto1 = nnexto;
			//~ nwin1 = nwin;
		//~ }
		//~ return 0;
		//~ cout << nnexto << ' ' << nnexte << ' ' << nwin << '\n';
		numnexte += nnexte; numnexto += nnexto; numwin += nwin;
	}
	
	
	//~ cout << ans << '\n';
	//~ DEC(j,D-1,1) ans = (numnexto - numnexte) * ans + N * numwin + qe9xp(N, 2*(D-j)-1) * numnexte;
	//~ cout << (nnexto1 - nnexte1) * ans + nwin1 * N + qexp(N, 2*D-1)* nnexte1;
	int x = ans; ans = 0;
	FOR(i,1,N){
		depth[i] = 0; dfs(i,-1); dfs2(i,-1);
		if (win[1]) (ans += N) %= MOD;
		else if (firstpar[1] == i){
			if (depth[1] % 2 == 0) (ans += N - x) %= MOD;
			else (ans += x) %= MOD;
		}else if ((depth[1] - depth[firstpar[1]]) % 2 == 1) (ans += N) %= MOD;
		
	}
	cout << ans;
}

Subtask #1
0.0 / 0.0

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

Subtask #2
0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	4 ms	9684 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	4 ms	9684 KB	Output is correct
2	Correct	5 ms	9684 KB	Output is correct
3	Correct	5 ms	9684 KB	Output is correct
4	Correct	8 ms	9676 KB	Output is correct
5	Correct	7 ms	9724 KB	Output is correct
6	Correct	6 ms	9684 KB	Output is correct

Subtask #4
15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	9684 KB	Output is correct
2	Correct	5 ms	9684 KB	Output is correct
3	Correct	5 ms	9684 KB	Output is correct
4	Correct	8 ms	9676 KB	Output is correct
5	Correct	7 ms	9724 KB	Output is correct
6	Correct	6 ms	9684 KB	Output is correct
7	Correct	74 ms	9812 KB	Output is correct
8	Correct	72 ms	9832 KB	Output is correct
9	Correct	730 ms	9780 KB	Output is correct
10	Correct	79 ms	9684 KB	Output is correct
11	Correct	79 ms	9776 KB	Output is correct

Subtask #5
0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	9684 KB	Output is correct
2	Correct	5 ms	9684 KB	Output is correct
3	Correct	5 ms	9684 KB	Output is correct
4	Correct	8 ms	9676 KB	Output is correct
5	Correct	7 ms	9724 KB	Output is correct
6	Correct	6 ms	9684 KB	Output is correct
7	Correct	74 ms	9812 KB	Output is correct
8	Correct	72 ms	9832 KB	Output is correct
9	Correct	730 ms	9780 KB	Output is correct
10	Correct	79 ms	9684 KB	Output is correct
11	Correct	79 ms	9776 KB	Output is correct
12	Execution timed out	1075 ms	20652 KB	Time limit exceeded
13	Halted	0 ms	0 KB	-

Subtask #6
0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	9684 KB	Output is correct
2	Correct	5 ms	9684 KB	Output is correct
3	Correct	5 ms	9684 KB	Output is correct
4	Correct	8 ms	9676 KB	Output is correct
5	Correct	7 ms	9724 KB	Output is correct
6	Correct	6 ms	9684 KB	Output is correct
7	Correct	74 ms	9812 KB	Output is correct
8	Correct	72 ms	9832 KB	Output is correct
9	Correct	730 ms	9780 KB	Output is correct
10	Correct	79 ms	9684 KB	Output is correct
11	Correct	79 ms	9776 KB	Output is correct
12	Correct	6 ms	9692 KB	Output is correct
13	Incorrect	87 ms	9684 KB	Output isn't correct
14	Halted	0 ms	0 KB	-

Subtask #7
0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	9684 KB	Output is correct
2	Correct	5 ms	9684 KB	Output is correct
3	Correct	5 ms	9684 KB	Output is correct
4	Correct	8 ms	9676 KB	Output is correct
5	Correct	7 ms	9724 KB	Output is correct
6	Correct	6 ms	9684 KB	Output is correct
7	Correct	74 ms	9812 KB	Output is correct
8	Correct	72 ms	9832 KB	Output is correct
9	Correct	730 ms	9780 KB	Output is correct
10	Correct	79 ms	9684 KB	Output is correct
11	Correct	79 ms	9776 KB	Output is correct
12	Execution timed out	1075 ms	20652 KB	Time limit exceeded
13	Halted	0 ms	0 KB	-

Subtask #8
0 / 15.0

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

Submission #588776

Compilation message