QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#243956#7607. The Doubling Game 2JWRuixiRE 6ms24540kbC++232.8kb2023-11-08 19:39:342023-11-08 19:39:35

Judging History

你现在查看的是最新测评结果

  • [2023-11-08 19:39:35]
  • 评测
  • 测评结果:RE
  • 用时:6ms
  • 内存:24540kb
  • [2023-11-08 19:39:34]
  • 提交

answer

#include <bits/stdc++.h>
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2")
// #define ATC
#define LL long long
#define eb emplace_back
#define writesp(x) write(x), putchar(' ')
#define writeln(x) write(x), putchar('\n')
#define FIO(FILENAME) freopen(FILENAME".in", "r", stdin), freopen(FILENAME".out", "w", stdout)
using namespace std;

#ifdef ATC
#include <atcoder/all>
using namespace atcoder;
#endif

namespace IO {
	char ibuf[(1 << 20) + 1], *iS, *iT;
#if ONLINE_JUDGE
#define gh() (iS == iT ? iT = (iS = ibuf) + fread(ibuf, 1, (1 << 20) + 1, stdin), (iS == iT ? EOF : *iS++) : *iS++)
#else
#define gh() getchar()
#endif
	inline long long read() {
		char ch = gh();
		long long x = 0;
		bool t = 0;
		while (ch < '0' || ch > '9') t |= ch == '-', ch = gh();
		while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (ch ^ 48), ch = gh();
		return t ? ~(x - 1) : x;
	}
	template<typename _Tp>
	inline void write(_Tp x) {
		static char stk[64], *top = stk;
		if (x < 0) {
			x = ~(x - 1);
			putchar('-');
		}
		do *top++ = x % 10, x /= 10;
		while (x);
		while (top != stk) putchar((*--top) | 48);
	}
}

using IO::read;
using IO::write;

using vi = vector<int>;

constexpr int N = 3e5 + 9, mod = 1e9 + 7;
int n, h[N];
vi G[N], f[N], g[N];

template<typename T, typename _T>
inline void inc (T &x, const _T &y) {
	(x += y) >= mod && (x -= mod);
}

inline void dfs (int u, int fa) {
	if (fa) {
		G[u].erase(find(G[u].begin(), G[u].end(), fa));
	}
	for (int v : G[u]) {
		dfs(v, u);
	}
	sort(G[u].begin(), G[u].end(), [](int i, int j) {
		return f[i].size() < f[j].size();
	});
	int o = 1;
	vi U{1, 0}, D{0, 0};
	for (int v : G[u]) {
		int L = f[v].size();
		vi F(1 << L), G(1 << L);
		for (int i = 0; i < (1 << o); i++) {
			inc(F[i], (LL)U[i] * h[v] % mod);
			inc(G[i], (LL)D[i] * h[v] % mod);
			for (int j = 0; j < L; j++) {
				if (i >> j & 1) continue;
				inc(F[i | (1 << j)], (LL)U[i] * f[v][j] % mod);
				if (i > (1 << j)) {
					inc(G[i | (1 << j)], (LL)D[i] * f[v][j] % mod);
				} else {
					inc(G[i | (1 << j)], (LL)U[i] * g[v][j] % mod);
				}
			}
		}
		U.swap(F);
		D.swap(G);
		o = L;
	}
	f[u].resize(o + 1);
	g[u].resize(o + 1);
	LL all = 0;
	for (int i = 0; i < o + 1; i++) {
		int j = (1 << i) - 1;
		all += U[j] + D[j];
		f[u][i] = g[u][i] = U[j];
		for (int k = 0; k < i - 1; k++) inc(g[u][k], U[j ^ (1 << k)]);
	}
	h[u] = all % mod;
	int p = (1 << o) - 1;
	while (p && !f[u][p] && !g[u][p]) --p;
	f[u].erase(f[u].begin() + p + 1, f[u].end());
	g[u].erase(g[u].begin() + p + 1, g[u].end());
}

int main() {
	n = read();
	for (int i = 1, u, v; i < n; i++) {
		u = read(), v = read();
		G[u].eb(v);
		G[v].eb(u);
	}
	dfs(1, 0);
	write(h[1]);
}
// I love WHQ!

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 6ms
memory: 24540kb

input:

5
1 2
1 3
1 4
4 5

output:

21

result:

ok single line: '21'

Test #2:

score: 0
Accepted
time: 0ms
memory: 24476kb

input:

1

output:

1

result:

ok single line: '1'

Test #3:

score: -100
Runtime Error

input:

128
11 32
116 81
65 4
117 47
5 81
104 30
61 8
82 59
95 20
92 29
29 127
97 39
123 33
59 128
115 33
83 67
74 16
77 33
64 73
124 123
8 127
61 51
101 122
35 90
119 116
112 27
81 93
109 123
54 1
119 100
116 16
65 47
67 27
22 105
76 87
36 39
27 96
72 31
91 123
21 105
118 12
110 48
121 72
14 115
24 16
106 ...

output:


result: