QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#46860#4665. Contemporary ArtistQingyuRE 2ms3940kbC++231.2kb2022-09-02 01:10:592022-09-02 01:11:04

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-09-02 01:11:04]
  • 评测
  • 测评结果：RE
  • 用时：2ms
  • 内存：3940kb
查看
  • [2022-09-02 01:10:59]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
int n, k;
vector <int> son[1010];
int id[1010], dep[1010];
int f[1010];
void dfs(int cur, int fa) {
    f[cur] = fa;
    dep[cur] = dep[fa] + 1;
    for (auto i : son[cur]) if (i != fa) dfs(i, cur);
}
int cnt[1010][1010];
int main() {
    scanf("%d%d", &n, &k);
    for (int i = 1; i < n; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        son[u].push_back(v);
        son[v].push_back(u);
    }
    dfs(1, 0);
    for (int i = 1; i <= n; i++) id[i] = i, son[i].clear();
    sort(id + 1, id + 1 + n, [](int x, int y) {
        return dep[x] < dep[y];
    });
    int ans = n;
    for (int i = 2; i <= n; i++) {
        int cur = id[i];
        son[cur].push_back(f[cur]);
        son[f[cur]].push_back(cur);
        memset(dep, 0, sizeof dep);
        dfs(cur, 0);
        for (int j = 1; j <= n; j++) if (dep[j]) cnt[cur][dep[j] - 1]++;
        for (int j = 1; j <= n; j++) {
            cnt[cur][j] += cnt[cur][j - 1];
            if (cnt[cur][j] > k) ans = min(ans, j - 1);
        }
    }
    int ans2 = k;
    for (int i = 2; i <= n; i++) ans2 = 1ll * ans2 * (k - cnt[i][ans] + 1) % 998244353;
    cout << ans + 1 << ' ' << ans2 << endl;
}
Source code, Language: C++23

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 3868kb

input:

4 2
1 2
1 3
1 4

output:

2 2

result:

ok 2 number(s): "2 2"

Test #2:

score: 0
Accepted
time: 2ms
memory: 3868kb

input:

4 3
1 2
1 3
1 4

output:

2 24

result:

ok 2 number(s): "2 24"

Test #3:

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

input:

5 4
1 2
1 3
1 4
4 5

output:

3 48

result:

ok 2 number(s): "3 48"

Test #4:

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

input:

2 1
1 2

output:

1 1

result:

ok 2 number(s): "1 1"

Test #5:

score: 0
Accepted
time: 1ms
memory: 3824kb

input:

10 8
1 7
8 1
3 1
1 2
1 9
1 10
5 1
4 1
1 6

output:

2 322828856

result:

ok 2 number(s): "2 322828856"

Test #6:

score: 0
Accepted
time: 2ms
memory: 3688kb

input:

10 8
2 7
8 2
3 2
1 2
2 9
2 10
5 2
4 2
2 6

output:

2 322828856

result:

ok 2 number(s): "2 322828856"

Test #7:

score: 0
Accepted
time: 2ms
memory: 3892kb

input:

10 8
6 7
8 7
3 2
1 2
8 9
9 10
5 4
4 3
5 6

output:

8 40320

result:

ok 2 number(s): "8 40320"

Test #8:

score: 0
Accepted
time: 2ms
memory: 3820kb

input:

10 1
5 10
1 2
7 3
2 4
3 1
4 8
5 2
3 6
9 4

output:

1 1

result:

ok 2 number(s): "1 1"

Test #9:

score: 0
Accepted
time: 1ms
memory: 3844kb

input:

14 7
9 3
3 10
1 3
2 6
2 7
3 13
12 3
5 2
4 2
3 11
8 2
14 3
1 2

output:

2 584621989

result:

ok 2 number(s): "2 584621989"

Test #10:

score: 0
Accepted
time: 2ms
memory: 3852kb

input:

20 12
2 11
9 1
3 2
2 14
1 2
20 5
8 6
18 12
5 1
16 9
12 6
13 9
12 17
19 13
15 8
9 10
1 4
6 2
6 7

output:

4 411254173

result:

ok 2 number(s): "4 411254173"

Test #11:

score: 0
Accepted
time: 2ms
memory: 3940kb

input:

21 5
16 19
1 20
6 12
1 8
7 1
1 3
4 1
14 8
11 16
11 13
1 2
15 17
1 9
10 15
3 6
21 1
10 9
5 4
1 18
11 1

output:

2 226486909

result:

ok 2 number(s): "2 226486909"

Test #12:

score: 0
Accepted
time: 2ms
memory: 3936kb

input:

22 17
19 20
2 5
9 8
4 3
1 2
17 16
6 5
10 11
2 3
7 6
19 10
12 13
18 6
14 15
21 20
7 8
22 21
6 10
12 9
13 14
16 10

output:

8 714329934

result:

ok 2 number(s): "8 714329934"

Test #13:

score: 0
Accepted
time: 2ms
memory: 3796kb

input:

23 20
13 9
3 6
4 7
17 23
14 19
16 22
15 21
6 10
3 1
4 2
12 17
2 1
6 9
5 3
8 5
8 12
7 11
10 14
11 16
15 20
13 18
10 15

output:

10 91151912

result:

ok 2 number(s): "10 91151912"

Test #14:

score: 0
Accepted
time: 2ms
memory: 3740kb

input:

24 21
3 6
2 1
19 22
9 12
11 8
14 11
21 18
4 1
19 16
15 18
4 7
20 17
10 13
6 9
15 12
16 13
17 14
24 21
3 1
7 10
23 20
8 5
2 5

output:

14 125580172

result:

ok 2 number(s): "14 125580172"

Test #15:

score: 0
Accepted
time: 2ms
memory: 3800kb

input:

24 6
14 8
16 10
13 7
9 3
13 19
8 2
14 20
23 17
5 1
3 1
6 12
4 1
10 4
2 1
11 5
15 21
1 6
1 7
22 16
18 12
11 17
18 24
15 9

output:

2 239743846

result:

ok 2 number(s): "2 239743846"

Test #16:

score: -100
Runtime Error

input:

2000 1971
416 1
1 1255
1 841
1011 1
1 430
1 649
1 1389
794 1
1784 1
1931 1
1237 1
1 351
1385 1
1675 1
1 1073
571 1
1518 1
1 510
1 108
634 1
1 1639
1489 1
1291 1
1 516
1 1001
1 29
1 728
1 648
1 146
1 1846
1 1757
1451 1
1 230
605 1
877 1
469 1
1 1390
1 32
532 1
1 468
1647 1
1 784
1 1892
1574 1
750 1
5...

output:

result:
English 繁體中文 简体中文

Server Time: 2024-12-02 10:04:43 | OpenSource Project