답안 #588776

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
588776 2022-07-04T04:34:08 Z jiahng Star Trek (CEOI20_startrek) C++14
23 / 100
1000 ms 20652 KB
#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;
}

# 결과 실행 시간 메모리 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 -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 9684 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 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
# 결과 실행 시간 메모리 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
# 결과 실행 시간 메모리 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 -
# 결과 실행 시간 메모리 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 -
# 결과 실행 시간 메모리 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 -
# 결과 실행 시간 메모리 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 -