| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 501188 |
2022-01-02T15:02:49 Z |
rainboy |
Wells (CEOI21_wells) |
C |
|
1 ms |
332 KB |
#include <stdio.h>
#include <string.h>
#define N 10000
#define INF 0x3f3f3f3f3f3f3f3fLL
#define MD 1000000007
long long min(long long a, long long b) { return a < b ? a : b; }
int max(int a, int b) { return a > b ? a : b; }
int mem[(N - 1) * 2], *p = mem, *ej[N], eo[N], n, k;
int ll[N], jj[N], ta[N], tb[N], kk[N + 1], qu[N * 2];
void dfs1(int p, int i, int d) {
int o;
kk[d + 1]++;
ll[i] = 0, jj[i] = -1;
for (o = eo[i]; o--; ) {
int j = ej[i][o];
if (j != p) {
dfs1(i, j, d + 1);
if (ll[i] < ll[j])
ll[i] = ll[j], jj[i] = j;
}
}
ll[i]++;
}
void dfs2(int p, int i, int d) {
static int time;
int o;
qu[ta[i] = time++] = i, tb[i] = kk[d]++;
if (jj[i] != -1)
dfs2(i, jj[i], d + 1);
else
time++;
for (o = eo[i]; o--; ) {
int j = ej[i][o];
if (j != p && j != jj[i])
dfs2(i, j, d + 1);
}
}
int cnt[N * 2]; long long xx[N + 1];
void get_range(int a, int *l, int *r) {
*l = tb[qu[a]], *r = *l + cnt[a];
}
void dfs3(int p, int i) {
int o, d, l1, r1, l2, r2;
long long c;
for (o = eo[i]; o--; ) {
int j = ej[i][o];
if (j != p)
dfs3(i, j);
}
if (k <= ll[i]) {
get_range(ta[i] + k - 1, &l1, &r1);
xx[l1]++, xx[r1]--;
if (p != -1)
xx[tb[p]] -= r1 - l1, xx[tb[p] + 1] += r1 - l1;
}
cnt[ta[i]]++;
for (o = eo[i]; o--; ) {
int j = ej[i][o];
if (j != p && j != jj[i]) {
for (d = 1; d <= ll[j] && d < k; d++)
if (k - d <= ll[i]) {
get_range(ta[i] + k - d - 1, &l1, &r1), get_range(ta[j] + d - 1, &l2, &r2);
c = (long long) (r1 - l1) * (r2 - l2);
xx[l1] += r2 - l2, xx[r1] -= r2 - l2;
xx[l2] += r1 - l1, xx[r2] -= r1 - l1;
xx[tb[i]] -= c, xx[tb[i] + 1] += c;
if (p != -1)
xx[tb[p]] -= c, xx[tb[p] + 1] += c;
}
for (d = 1; d <= ll[j]; d++)
cnt[ta[i] + d] += cnt[ta[j] + d - 1];
}
}
}
long long ww[N];
void dfs4(int p, int i) {
int o;
ww[i] = xx[tb[i]];
for (o = eo[i]; o--; ) {
int j = ej[i][o];
if (j != p) {
dfs4(i, j);
ww[i] += ww[j];
}
}
}
long long dp[N * 2]; int dq[N * 2];
void dfs5(int p, int i) {
int o, j, di, dj, d;
long long pi, pj, p_;
int qi, qj, q;
dp[ta[i] + 0] = ww[i], dq[ta[i] + 0] = 1;
if (jj[i] == -1)
dp[ta[i] + 1] = 0, dq[ta[i] + 1] = 1;
else {
for (o = eo[i]; o--; ) {
j = ej[i][o];
if (j != p)
dfs5(i, j);
}
pi = dp[ta[i] + 0];
qi = dq[ta[i] + 0];
dp[ta[i] + 0] = INF, dq[ta[i] + 0] = 0;
for (dj = ll[jj[i]]; dj >= 0; dj--) {
pj = dp[ta[jj[i]] + dj];
qj = dq[ta[jj[i]] + dj];
p_ = pi + pj;
q = (long long) qi * qj % MD;
if (dp[ta[i] + 0] > p_)
dp[ta[i] + 0] = p_, dq[ta[i] + 0] = 0;
if (dp[ta[i] + 0] == p_)
dq[ta[i] + 0] = (dq[ta[i] + 0] + q) % MD;
}
for (o = eo[i]; o--; ) {
j = ej[i][o];
if (j != p && j != jj[i])
for (di = ll[i]; di >= 0; di--) {
pi = dp[ta[i] + di];
qi = dq[ta[i] + di];
dp[ta[i] + di] = INF, dq[ta[i] + di] = 0;
for (dj = ll[j]; dj >= 0; dj--) {
pj = dp[ta[j] + dj];
qj = dq[ta[j] + dj];
if (di + dj < k) {
d = di == 0 ? 0 : max(di, dj + 1);
p_ = pi + pj;
q = (long long) qi * qj % MD;
if (dp[ta[i] + d] > p_)
dp[ta[i] + d] = p_, dq[ta[i] + d] = 0;
if (dp[ta[i] + d] == p_)
dq[ta[i] + d] = (dq[ta[i] + d] + q) % MD;
}
}
}
}
}
}
int main() {
static int uu[N - 1], vv[N - 1];
int h, i, j, d, yes, q;
long long w;
scanf("%d%d", &n, &k);
for (h = 0; h < n - 1; h++) {
scanf("%d%d", &i, &j), i--, j--;
uu[h] = i, vv[h] = j;
eo[i]++, eo[j]++;
}
for (i = 0; i < n; i++) {
ej[i] = p, p += eo[i];
eo[i] = 0;
}
for (h = 0; h < n - 1; h++) {
i = uu[h], j = vv[h];
ej[i][eo[i]++] = j, ej[j][eo[j]++] = i;
}
dfs1(-1, 0, 0);
for (d = 1; d <= n; d++)
kk[d] += kk[d - 1];
memset(qu, -1, n * 2 * sizeof *qu);
dfs2(-1, 0, 0);
dfs3(-1, 0);
for (i = 1; i <= n; i++)
xx[i] += xx[i - 1];
dfs4(-1, 0);
w = 0;
for (i = 0; i < n; i++)
w += ww[i];
w /= k;
dfs5(-1, 0);
yes = 0, q = 0;
for (d = 0; d <= ll[0]; d++)
if (dp[ta[0] + d] == w)
yes = 1, q = (q + dq[ta[0] + d]) % MD;
printf(yes ? "YES\n" : "NO\n");
printf("%d\n", q);
return 0;
}
Compilation message
wells.c: In function 'main':
wells.c:167:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
167 | scanf("%d%d", &n, &k);
| ^~~~~~~~~~~~~~~~~~~~~
wells.c:169:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
169 | scanf("%d%d", &i, &j), i--, j--;
| ^~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
332 KB |
Output is correct |
| 2 |
Partially correct |
1 ms |
332 KB |
Output is partially correct |
| 3 |
Partially correct |
0 ms |
332 KB |
Output is partially correct |
| 4 |
Incorrect |
0 ms |
276 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
332 KB |
Output is correct |
| 2 |
Partially correct |
1 ms |
332 KB |
Output is partially correct |
| 3 |
Partially correct |
0 ms |
332 KB |
Output is partially correct |
| 4 |
Incorrect |
0 ms |
276 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
332 KB |
Output is correct |
| 2 |
Partially correct |
1 ms |
332 KB |
Output is partially correct |
| 3 |
Partially correct |
0 ms |
332 KB |
Output is partially correct |
| 4 |
Incorrect |
0 ms |
276 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
332 KB |
Output is correct |
| 2 |
Partially correct |
1 ms |
332 KB |
Output is partially correct |
| 3 |
Partially correct |
0 ms |
332 KB |
Output is partially correct |
| 4 |
Incorrect |
0 ms |
276 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
