oj.uz

Submission #589189

# Submission time Handle Problem Language Result Execution time Memory
589189 2022-07-04T10:14:01 Z jiahng Star Trek (CEOI20_startrek) C++14
50 / 100
 1000 ms 20864 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define int ll
typedef pair<int,int> 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);
}
bool gwin[maxn];
int sm[maxn];

void dfs3(int x,int p){
	int n = 0;
	gwin[x] = win[x];
	aFOR(i,adj[x]) n += !win[i];
	aFOR(i,adj[x]) if (i != p){
		bool iwini = win[i];
		win[x] = (n-1 > 0);
		win[i] |= !win[x];
		
		sm[x] -= !iwini;
		sm[x] += win[x] - (n > 0);
		
		sm[i] += win[x];
		sm[i] += win[i] - iwini;
		
		dfs3(i,x);
		win[x] = (n > 0);
		win[i] = iwini;
	}
}

void dfs4(int x,int p){
	
	
	
}
int qexp(int a,int b){
	int ans = 1;
	while (b){
		//~ cout << a << ' ' << b << ' ' << ans << '\n';
		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);
	}
	//~ cout << qexp(N, 2 * D);
	//~ return 0;
	int numnexte = 0,numnexto = 0, numwin = 0;
	
	int ans = 0;
	int nnexte1 = 0, nnexto1 = 0, nwin1 = 0;
	
	depth[1] = 0; dfs(1,-1); dfs2(1,-1); dfs3(1,-1);
	
	FOR(i,1,N){
		depth[i] = 0; dfs(i,-1); dfs2(i,-1);
		ans += win[i];
		//~ FOR(j,1,N) 
		int nnexte = 0,nnexto = 0, nwin = 0;
		FOR(j,1,N){
			if (win[j]){
				nwin++;
				if (j == 1) nwin1++;
			}else if (firstpar[j] == i){
				if (depth[j] % 2 == 0){
					nnexte++; if (j == 1) nnexte1++;
				}else{
					nnexto++; if (j == 1) nnexto1++;
				}
			
			}else if ((depth[j] - depth[firstpar[j]]) % 2 == 1){
				nwin++; if (j == 1) nwin1++;
			}
		}
		numnexte += nnexte; numnexto += nnexto; numwin += nwin;
	}
	//~ cout << nnexte1 << ' ' << nnexto1 << '\n';
	nnexte1 = nnexto1 = 0;
	depth[1] = 0;dfs(1,-1); dfs2(1,-1);
	//~ FOR(i,1,N) cout << firstpar[i] << ' ';
	//~ cout << '\n';
	FOR(i,1,N) if (firstpar[i] == 1 && !win[i]){
		if (depth[i] % 2 == 0) nnexte1++;
		else nnexto1++;
	}
	//~ cout << nnexte1 << ' ' << nnexto1 << '\n';
	if (D > 1){
		int m = numnexto - numnexte, c = numwin + numnexte;
		
		
		int r = (m * qexp((N*N)%MOD, MOD - 2)) % MOD; //mN^-2
		
		ans = (qexp(m, D - 1) * ans) % MOD;
		
		int geomseries = ((qexp(r, D - 1) - 1) * qexp(r - 1, MOD - 2)) % MOD;
		ans += (((geomseries * qexp(N, 2*(D-1)-1)) % MOD) * c) % MOD;
		(ans += MOD) %= MOD;
	}
		
	ans = (((nnexto1 - nnexte1) * ans) % MOD + (qexp(N, 2*D-1)* (nwin1 + nnexte1)) % MOD) % MOD;
	cout << (ans + MOD) % MOD;
}

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 59 ms 9684 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9720 KB Output is correct
3 Correct 5 ms 9724 KB Output is correct
4 Correct 5 ms 9728 KB Output is correct
5 Correct 5 ms 9684 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9628 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 6 ms 9728 KB Output is correct
5 Correct 5 ms 9684 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 5 ms 9628 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 6 ms 9728 KB Output is correct
5 Correct 5 ms 9684 KB Output is correct
6 Correct 6 ms 9684 KB Output is correct
7 Correct 50 ms 9932 KB Output is correct
8 Correct 47 ms 9868 KB Output is correct
9 Correct 386 ms 9800 KB Output is correct
10 Correct 56 ms 9812 KB Output is correct
11 Correct 47 ms 9812 KB Output is correct

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9628 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 6 ms 9728 KB Output is correct
5 Correct 5 ms 9684 KB Output is correct
6 Correct 6 ms 9684 KB Output is correct
7 Correct 50 ms 9932 KB Output is correct
8 Correct 47 ms 9868 KB Output is correct
9 Correct 386 ms 9800 KB Output is correct
10 Correct 56 ms 9812 KB Output is correct
11 Correct 47 ms 9812 KB Output is correct
12 Execution timed out 1092 ms 20864 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9628 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 6 ms 9728 KB Output is correct
5 Correct 5 ms 9684 KB Output is correct
6 Correct 6 ms 9684 KB Output is correct
7 Correct 50 ms 9932 KB Output is correct
8 Correct 47 ms 9868 KB Output is correct
9 Correct 386 ms 9800 KB Output is correct
10 Correct 56 ms 9812 KB Output is correct
11 Correct 47 ms 9812 KB Output is correct
12 Correct 5 ms 9684 KB Output is correct
13 Correct 52 ms 9812 KB Output is correct
14 Correct 6 ms 9688 KB Output is correct
15 Correct 5 ms 9632 KB Output is correct
16 Correct 5 ms 9684 KB Output is correct
17 Correct 6 ms 9684 KB Output is correct
18 Correct 6 ms 9720 KB Output is correct
19 Correct 6 ms 9684 KB Output is correct
20 Correct 5 ms 9684 KB Output is correct
21 Correct 44 ms 9816 KB Output is correct
22 Correct 48 ms 9940 KB Output is correct
23 Correct 374 ms 9812 KB Output is correct
24 Correct 54 ms 9812 KB Output is correct
25 Correct 45 ms 9724 KB Output is correct
26 Correct 51 ms 9812 KB Output is correct
27 Correct 47 ms 9856 KB Output is correct
28 Correct 201 ms 9784 KB Output is correct
29 Correct 54 ms 9812 KB Output is correct
30 Correct 53 ms 9812 KB Output is correct

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9628 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 6 ms 9728 KB Output is correct
5 Correct 5 ms 9684 KB Output is correct
6 Correct 6 ms 9684 KB Output is correct
7 Correct 50 ms 9932 KB Output is correct
8 Correct 47 ms 9868 KB Output is correct
9 Correct 386 ms 9800 KB Output is correct
10 Correct 56 ms 9812 KB Output is correct
11 Correct 47 ms 9812 KB Output is correct
12 Execution timed out 1092 ms 20864 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 Correct 59 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 5 ms 9720 KB Output is correct
5 Correct 5 ms 9724 KB Output is correct
6 Correct 5 ms 9728 KB Output is correct
7 Correct 5 ms 9684 KB Output is correct
8 Correct 5 ms 9628 KB Output is correct
9 Correct 5 ms 9684 KB Output is correct
10 Correct 5 ms 9684 KB Output is correct
11 Correct 6 ms 9728 KB Output is correct
12 Correct 5 ms 9684 KB Output is correct
13 Correct 6 ms 9684 KB Output is correct
14 Correct 50 ms 9932 KB Output is correct
15 Correct 47 ms 9868 KB Output is correct
16 Correct 386 ms 9800 KB Output is correct
17 Correct 56 ms 9812 KB Output is correct
18 Correct 47 ms 9812 KB Output is correct
19 Execution timed out 1092 ms 20864 KB Time limit exceeded
20 Halted 0 ms 0 KB -