oj.uz

Submission #482427

# Submission time Handle Problem Language Result Execution time Memory
482427 2021-10-24T14:24:47 Z pooyashams Star Trek (CEOI20_startrek) C++17
45 / 100
 119 ms 64388 KB 
#include <algorithm>
#include <numeric>
#include <iostream>
#include <cstring>
#include <cmath>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cassert>

using namespace std;
typedef long long ll;

const int maxn = 2e5+10;
const int mod = 1e9+7;

struct mat
{
	vector<vector<ll>> vals;
	int n, m;
	mat(int _n, int _m, bool I=false)
	{
		n = _n;
		m = _m;
		vals = vector<vector<ll>>(n);
		fill(vals.begin(), vals.end(), vector<ll>(m, 0));
		if(I and n == m)
			for(int i = 0; i < n; i++)
				vals[i][i] = 1;
	}
	inline vector<ll>& operator[](int i)
	{
		return vals[i];
	}
	inline mat operator*(const mat &other)
	{
		assert(m == other.n);
		mat out(n, other.m, false);
		for(int i = 0; i < n; i++)
			for(int k = 0; k < m; k++)
				for(int j = 0; j < other.m; j++)
					out[i][j] = (out[i][j] + vals[i][k] * other.vals[k][j]) % mod;
		return out;
	}
};

inline ll bpow(ll x, ll y)
{
	x = x%mod;
	ll ans = 1;
	while(y > 0)
	{
		if(y & 1)
			ans = ans * x % mod;
		x = x*x % mod;
		y >>= 1;
	}
	return ans;
}

inline mat mpow(mat x, ll y)
{
	mat ans(x.n, x.n, true);
	while(y > 0)
	{
		if(y & 1)
			ans = ans * x;
		x = x*x;
		y >>= 1;
	}
	return ans;
}

inline ll inv(ll x)
{
	return bpow(x, mod-2);
}

vector<int> G[maxn];
vector<int> kids[maxn];
int par[maxn];

bool vis[maxn];
bool wndn[maxn];
bool wnup[maxn];

int crdn[maxn];
int crup[maxn];

bool finwn[maxn];
int fincr[maxn];

void dfs1(int v)
{
	if(vis[v]) return;
	vis[v] = true;
	for(int u: G[v])
	{
		if(vis[u])
		{
			par[v] = u;
		}
		else
		{
			dfs1(u);
			kids[v].push_back(u);
		}
	}
}

void dfswndn(int v)
{
	for(int u: kids[v])
	{
		dfswndn(u);
		wndn[v] = wndn[v] or (!wndn[u]);
	}
}

void dfswnup(int v) // wnup[v] is set
{
	bool pso = wnup[v];
	for(auto u = kids[v].rbegin(); u != kids[v].rend(); u++)
	{
		wnup[*u] = pso;
		pso = pso or (!wndn[*u]);
	}
	pso = wnup[v];
	for(int u: kids[v])
	{
		wnup[u] = !(wnup[u] or pso);
		pso = pso or (!wndn[u]);
	}
	for(int u: kids[v])
		dfswnup(u);
}

void dfscrdn(int v)
{
	for(int u: kids[v])
		dfscrdn(u);
	crdn[v] = !wndn[v];
	if(!wndn[v])
	{
		for(int u: kids[v])
			crdn[v] += crdn[u];
	}
	else
	{
		int lc = 0;
		int cr = 0;
		for(int u: kids[v])
		{
			lc += !wndn[u];
			if(!wndn[u])
				cr += crdn[u];
		}
		if(lc == 1)
			crdn[v] += cr;
	}
}

void dfscrup(int v) // crup[v] is set
{
	vector<int> rlc(kids[v].size());
	vector<int> llc(kids[v].size());
	vector<int> rls(kids[v].size());
	vector<int> lls(kids[v].size());
	vector<int> rsum(kids[v].size());
	vector<int> lsum(kids[v].size());
	int lc = 0;
	int ls = 0;
	int s = 0;
	for(int i = 0; i < (int)(kids[v].size()); i++)
	{
		int u = kids[v][i];
		llc[i] = lc;
		lls[i] = ls;
		lsum[i] = s;
		lc += !wndn[u];
		ls += (!wndn[u]) * crdn[u];
		s += crdn[u];
	}
	lc = 0;
	ls = 0;
	s = 0;
	for(int i = (int)(kids[v].size()) - 1; i >= 0; i--)
	{
		int u = kids[v][i];
		rlc[i] = lc;
		rls[i] = ls;
		rsum[i] = s;
		lc += !wndn[u];
		ls += (!wndn[u]) * crdn[u];
		s += crdn[u];
	}
	for(int i = 0; i < (int)(kids[v].size()); i++)
	{
		int u = kids[v][i];
		if(wnup[u])
		{
			crup[u] = crup[v] + lsum[i] + rsum[i];
		}
		else
		{
			crup[u] = 1;
			if(llc[i] + rlc[i] + wnup[v] == 1)
				crup[u] += (wnup[v] * crup[v]) + lls[i] + rls[i];
		}
	}
	for(int u: kids[v])
		dfscrup(u);
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	ll n, D; cin >> n >> D;
	for(int i = 1; i < n; i++)
	{
		int x, y; cin >> x >> y;
		x--; y--;
		G[x].push_back(y);
		G[y].push_back(x);
	}
	dfs1(0);
	dfswndn(0);
	wnup[0] = false;
	dfswnup(0);
	dfscrdn(0);
	crup[0] = 1;
	dfscrup(0);
	for(int v = 0; v < n; v++)
	{
		finwn[v] = wndn[v] or wnup[v];
		if(finwn[v])
		{
			int lc = 0;
			int ls = 0;
			for(int u: kids[v])
			{
				lc += !wndn[u];
				ls += (!wndn[u]) * crdn[u];
			}
			lc += wnup[v];
			ls += wnup[v] * crup[v];
			if(lc == 1)
				fincr[v] = ls;
		}
		else
		{
			fincr[v] = crdn[v] + crup[v] - 1;
		}
	}
	ll E = 0;
	ll L = 0;
	for(int i = 0; i < n; i++)
	{
		L += (!finwn[i]);
		if(finwn[i])
			E += fincr[i];
		else
			E -= fincr[i];
	}
	mat them(2, 2, false);
	mat init(2, 1, false);
	them[0][0] = n*n % mod;
	them[0][1] = 0;
	them[1][0] = n*n % mod;
	them[1][1] = E;
	init[0][0] = L;
	init[1][0] = L;
	them = mpow(them, D-1);
	init = them * init;
	ll L0 = init[1][0];
	//cerr << L << " " << E << " " << L0 << endl;
	//cerr << bpow(n, 2*D) << endl;
	ll ans = 1ll * fincr[0] * L0 % mod;
	//cerr << ans << endl;
	if(finwn[0])
		ans = (bpow(n, 2*D) - ans + mod) % mod;
	cout << ans << endl;
	return 0;
}

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9676 KB Output is correct
2 Incorrect 7 ms 9804 KB Output isn't correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 9676 KB Output is correct
2 Correct 5 ms 9676 KB Output is correct
3 Correct 5 ms 9676 KB Output is correct
4 Correct 6 ms 9676 KB Output is correct
5 Correct 5 ms 9676 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9676 KB Output is correct
2 Correct 7 ms 9676 KB Output is correct
3 Correct 5 ms 9676 KB Output is correct
4 Correct 6 ms 9676 KB Output is correct
5 Correct 6 ms 9712 KB Output is correct
6 Correct 5 ms 9712 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9676 KB Output is correct
2 Correct 7 ms 9676 KB Output is correct
3 Correct 5 ms 9676 KB Output is correct
4 Correct 6 ms 9676 KB Output is correct
5 Correct 6 ms 9712 KB Output is correct
6 Correct 5 ms 9712 KB Output is correct
7 Correct 6 ms 10060 KB Output is correct
8 Correct 6 ms 10188 KB Output is correct
9 Correct 6 ms 9804 KB Output is correct
10 Correct 6 ms 9804 KB Output is correct
11 Correct 6 ms 9772 KB Output is correct

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9676 KB Output is correct
2 Correct 7 ms 9676 KB Output is correct
3 Correct 5 ms 9676 KB Output is correct
4 Correct 6 ms 9676 KB Output is correct
5 Correct 6 ms 9712 KB Output is correct
6 Correct 5 ms 9712 KB Output is correct
7 Correct 6 ms 10060 KB Output is correct
8 Correct 6 ms 10188 KB Output is correct
9 Correct 6 ms 9804 KB Output is correct
10 Correct 6 ms 9804 KB Output is correct
11 Correct 6 ms 9772 KB Output is correct
12 Correct 106 ms 39564 KB Output is correct
13 Correct 119 ms 64388 KB Output is correct
14 Correct 59 ms 18436 KB Output is correct
15 Correct 80 ms 18256 KB Output is correct
16 Correct 92 ms 18044 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9676 KB Output is correct
2 Correct 7 ms 9676 KB Output is correct
3 Correct 5 ms 9676 KB Output is correct
4 Correct 6 ms 9676 KB Output is correct
5 Correct 6 ms 9712 KB Output is correct
6 Correct 5 ms 9712 KB Output is correct
7 Correct 6 ms 10060 KB Output is correct
8 Correct 6 ms 10188 KB Output is correct
9 Correct 6 ms 9804 KB Output is correct
10 Correct 6 ms 9804 KB Output is correct
11 Correct 6 ms 9772 KB Output is correct
12 Correct 5 ms 9676 KB Output is correct
13 Incorrect 6 ms 9804 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9676 KB Output is correct
2 Correct 7 ms 9676 KB Output is correct
3 Correct 5 ms 9676 KB Output is correct
4 Correct 6 ms 9676 KB Output is correct
5 Correct 6 ms 9712 KB Output is correct
6 Correct 5 ms 9712 KB Output is correct
7 Correct 6 ms 10060 KB Output is correct
8 Correct 6 ms 10188 KB Output is correct
9 Correct 6 ms 9804 KB Output is correct
10 Correct 6 ms 9804 KB Output is correct
11 Correct 6 ms 9772 KB Output is correct
12 Correct 106 ms 39564 KB Output is correct
13 Correct 119 ms 64388 KB Output is correct
14 Correct 59 ms 18436 KB Output is correct
15 Correct 80 ms 18256 KB Output is correct
16 Correct 92 ms 18044 KB Output is correct
17 Correct 5 ms 9676 KB Output is correct
18 Incorrect 6 ms 9804 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #8
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9676 KB Output is correct
2 Incorrect 7 ms 9804 KB Output isn't correct