oj.uz

답안 #588797

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
588797 2022-07-04T05:15:38 Z jiahng Star Trek (CEOI20_startrek) C++14
23 / 100
 1000 ms 19644 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 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 (win[j]) nwin++;
			else if (firstpar[j] == i){
				if (depth[1] % 2 == 0) nnexte++;
				else nnexto++;
			}else if ((depth[j] - depth[firstpar[j]]) % 2 == 1) nwin++;
		}
		numnexte += nnexte; numnexto += nnexto; numwin += nwin;
	}
	
	
	//~ cout << ans << '\n';
	DEC(j,D-1,1) ans = (((numnexto - numnexte) * ans) % MOD + (qexp(N, 2*(D-j)-1) * (numnexte + numwin)) % MOD) % MOD;
	(ans += MOD) %= MOD;
	//~ 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

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 9712 KB Output is correct
2 Incorrect 105 ms 9776 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 6 ms 9704 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 9708 KB Output is correct
2 Correct 6 ms 9684 KB Output is correct
3 Correct 7 ms 9728 KB Output is correct
4 Correct 8 ms 9684 KB Output is correct
5 Correct 6 ms 9684 KB Output is correct
6 Correct 7 ms 9672 KB Output is correct

Subtask #4
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 9708 KB Output is correct
2 Correct 6 ms 9684 KB Output is correct
3 Correct 7 ms 9728 KB Output is correct
4 Correct 8 ms 9684 KB Output is correct
5 Correct 6 ms 9684 KB Output is correct
6 Correct 7 ms 9672 KB Output is correct
7 Correct 102 ms 9856 KB Output is correct
8 Correct 90 ms 9832 KB Output is correct
9 Correct 714 ms 9776 KB Output is correct
10 Correct 95 ms 9776 KB Output is correct
11 Correct 91 ms 9772 KB Output is correct

Subtask #5
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 9708 KB Output is correct
2 Correct 6 ms 9684 KB Output is correct
3 Correct 7 ms 9728 KB Output is correct
4 Correct 8 ms 9684 KB Output is correct
5 Correct 6 ms 9684 KB Output is correct
6 Correct 7 ms 9672 KB Output is correct
7 Correct 102 ms 9856 KB Output is correct
8 Correct 90 ms 9832 KB Output is correct
9 Correct 714 ms 9776 KB Output is correct
10 Correct 95 ms 9776 KB Output is correct
11 Correct 91 ms 9772 KB Output is correct
12 Execution timed out 1083 ms 19644 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 9708 KB Output is correct
2 Correct 6 ms 9684 KB Output is correct
3 Correct 7 ms 9728 KB Output is correct
4 Correct 8 ms 9684 KB Output is correct
5 Correct 6 ms 9684 KB Output is correct
6 Correct 7 ms 9672 KB Output is correct
7 Correct 102 ms 9856 KB Output is correct
8 Correct 90 ms 9832 KB Output is correct
9 Correct 714 ms 9776 KB Output is correct
10 Correct 95 ms 9776 KB Output is correct
11 Correct 91 ms 9772 KB Output is correct
12 Correct 7 ms 9684 KB Output is correct
13 Incorrect 106 ms 9776 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 9708 KB Output is correct
2 Correct 6 ms 9684 KB Output is correct
3 Correct 7 ms 9728 KB Output is correct
4 Correct 8 ms 9684 KB Output is correct
5 Correct 6 ms 9684 KB Output is correct
6 Correct 7 ms 9672 KB Output is correct
7 Correct 102 ms 9856 KB Output is correct
8 Correct 90 ms 9832 KB Output is correct
9 Correct 714 ms 9776 KB Output is correct
10 Correct 95 ms 9776 KB Output is correct
11 Correct 91 ms 9772 KB Output is correct
12 Execution timed out 1083 ms 19644 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #8
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 9712 KB Output is correct
2 Incorrect 105 ms 9776 KB Output isn't correct
3 Halted 0 ms 0 KB -