Submission #871978

#	Time	Username	Problem	Language	Result	Execution time	Memory
871978		Trisanu_Das	Star Trek (CEOI20_startrek)	C++17	Compilation error	0 ms	0 KiB

startrek

#include "bits/stdc++.h"
using namespace std;
vector<int> adj[100005];
int dp[100005], up[100005], cnt[100005], n, sub[100005], rev[100005], tot[100005], tmp[100005];
 
void dfs(int u, int p = -1){
	for(auto v : adj[u]){
		if(v == p) continue;
		dfs(v, u);
		if(dp[v] == 0){
			dp[u] = 1; 
			tmp[u] += sub[v];
			cnt[u]++;
		} 
		tot[u] += sub[v];
	}
	
	if(cnt[u] > 1) sub[u] = 0;
	if(cnt[u] == 1) sub[u] = tmp[u];
	if(cnt[u] == 0) sub[u] = tot[u] + 1;
}
 
void re(int u, int p = -1){
	tot[u] += rev[u];
	if(up[u] == 0){
		tmp[u] += rev[u];
		dp[u] = 1, cnt[u]++;
	}
	if(cnt[u] > 1) sub[u] = 0;
	if(cnt[u] == 1) sub[u] = tmp[u];
	if(cnt[u] == 0) sub[u] = tot[u] + 1;
	for(auto v : adj[u]){
		if(v == p) continue;
		tot[u] -= sub[v];
		if(!dp[v]){
			cnt[u]--; tmp[u] -= sub[x];
		}
		if(cnt[u]) up[v] = 1;
		if(cnt[u] > 1) rev[v] = 0;
		if(cnt[u] == 1) rev[v] = tmp[u];
		if(cnt[u] == 0) rev[v] = tot[u] + 1;
		tot[u] += sub[x];
		if(!dp[x]){
			cnt[u]++; tmp[u] += sub[x];
		}
		re(x, u);
	}
}
 
int bp(int a, int b){
	int c = 1;
	while(b){
		if(b & 1) c = c * 1ll * a % mod;
		a = a * 1ll * a % mod, b >>= 1;
	} 
    return c;
}
 
signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	int d; cin>>n>>d;
	for(int i=1;i<n;i++){
		int a, b; cin>>a>>b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	
	dfs(1);
	up[1] = 1;
	re(1);
	int E = 0, L = 0;
	for(int i=1;i<=n;i++){
		if(dp[i] == 1) E = (E + sub[i]) % mod;
		else E = (E - sub[i] + mod) % mod, L++;
	}
	
	int F = n * 1ll * n % mod;
	int res = (bp(F, d) - bp(E, d) + mod) % mod * 1ll * bp((F - E + mod) % mod, mod - 2) % mod;
	res = res * 1ll * L % mod;
	if(dp[1]) res = res * 1ll * sub[1] % mod;
	else res = (bp(F, d) - res * 1ll * sub[1] % mod + mod) % mod;
	
	res = (bp(F, d) - res + mod) % mod;
	res = (res % mod + mod) % mod;
	cout<<res<<"\n";
}

Compilation message (stderr)

startrek.cpp: In function 'void re(int, int)':
startrek.cpp:36:28: error: 'x' was not declared in this scope
   36 |    cnt[u]--; tmp[u] -= sub[x];
      |                            ^
startrek.cpp:42:17: error: 'x' was not declared in this scope
   42 |   tot[u] += sub[x];
      |                 ^
startrek.cpp: In function 'int bp(int, int)':
startrek.cpp:53:31: error: 'mod' was not declared in this scope; did you mean 'modf'?
   53 |   if(b & 1) c = c * 1ll * a % mod;
      |                               ^~~
      |                               modf
startrek.cpp:54:21: error: 'mod' was not declared in this scope; did you mean 'modf'?
   54 |   a = a * 1ll * a % mod, b >>= 1;
      |                     ^~~
      |                     modf
startrek.cpp: In function 'int main()':
startrek.cpp:73:37: error: 'mod' was not declared in this scope; did you mean 'modf'?
   73 |   if(dp[i] == 1) E = (E + sub[i]) % mod;
      |                                     ^~~
      |                                     modf
startrek.cpp:74:26: error: 'mod' was not declared in this scope; did you mean 'modf'?
   74 |   else E = (E - sub[i] + mod) % mod, L++;
      |                          ^~~
      |                          modf
startrek.cpp:77:24: error: 'mod' was not declared in this scope; did you mean 'modf'?
   77 |  int F = n * 1ll * n % mod;
      |                        ^~~
      |                        modf