QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#286618	#7961. 一棵树	alpha1022	WA	291ms	142616kb	C++14	2.0kb	2023-12-18 08:42:19	2023-12-18 08:42:23

Judging History

This is the latest submission verdict.

[2023-12-18 08:42:23]
Judged

Verdict: WA
Time: 291ms
Memory: 142616kb

Show

[2023-12-18 08:42:19]
Submitted

answer

#include <bits/stdc++.h>

using namespace std;

using uint = unsigned;
using ll = long long;

const int N = 5e5;

int n, m;
vector<int> e[N + 5];

struct LeftistTree {
  struct node {
    int val, tag;
    int siz;
    int dis, ls, rs;
  } tr[N + 5];
  void pushUp(int u) { tr[u].dis = tr[tr[u].rs].dis + 1, tr[u].siz = tr[tr[u].ls].siz + 1 + tr[tr[u].rs].siz; }
  void apply(int k, int u) { tr[u].val += k, tr[u].tag += k; }
  void pushDown(int u) {
    if (!tr[u].tag) return ;
    if (tr[u].ls) apply(tr[u].tag, tr[u].ls);
    if (tr[u].rs) apply(tr[u].tag, tr[u].rs);
    tr[u].tag = 0;
  }
  int merge(int u, int v) {
    if (!u || !v) return u | v;
    if (tr[u].val < tr[v].val) swap(u, v);
    pushDown(u);
    tr[u].rs = merge(tr[u].rs, v);
    if (tr[tr[u].ls].dis < tr[tr[u].rs].dis) swap(tr[u].ls, tr[u].rs);
    pushUp(u);
    return u;
  }
  int pop(int u) {
    pushDown(u);
    int ret = merge(tr[u].ls, tr[u].rs);
    tr[u].siz = tr[u].dis = 1, tr[u].ls = tr[u].rs = 0;
    return ret;
  }
} lt;

int fa[N + 5], rt0[N + 5], rt1[N + 5];
void dfs(int u) {
  lt.tr[u].val = 0, lt.tr[u].siz = lt.tr[u].dis = 1, rt0[u] = u;
  for (int v: e[u])
    if (v != fa[u]) {
      fa[v] = u, dfs(v), lt.apply(-2, rt0[v]);
      if (rt1[v]) lt.tr[rt0[v]].val += (m & 1) << 1, lt.apply(2, rt1[v]);
      rt0[u] = lt.merge(rt0[u], rt0[v]), rt1[u] = lt.merge(rt1[u], rt1[v]);
    }
  while (lt.tr[rt0[u]].siz > (m + 1) >> 1) {
    int tmp = lt.pop(rt0[u]);
    rt1[u] = lt.merge(rt0[u], rt1[u]), rt0[u] = tmp;
  }
  for (; lt.tr[rt1[u]].siz > m >> 1; rt1[u] = lt.pop(rt1[u]));
}

ll ans;

int main() {
  scanf("%d%d", &n, &m);
  for (int i = 2; i <= n; ++i) { int u, v; scanf("%d%d", &u, &v), e[u].push_back(v), e[v].push_back(u); }
  if (m == 1) { printf("%d\n", n - 1); return 0; }
  dfs(1), ans = (ll)m * (n - 1);
  for (int rt = rt0[1]; rt; rt = lt.pop(rt)) ans += lt.tr[rt].val;
  for (int rt = rt1[1]; rt; rt = lt.pop(rt)) ans += lt.tr[rt].val;
  printf("%lld\n", ans);
}

源文件, 语言: C++14

詳細信息

Test #1:

score: 100

Accepted

time: 291ms

memory: 49288kb

input:

499991 31473
1 2
2 3
1 4
2 5
4 6
4 7
6 8
4 9
8 10
6 11
9 12
10 13
10 14
1 15
14 16
3 17
14 18
12 19
13 20
11 21
16 22
16 23
20 24
5 25
16 26
18 27
8 28
15 29
27 30
27 31
26 32
21 33
3 34
27 35
33 36
25 37
22 38
11 39
11 40
17 41
25 42
3 43
3 44
2 45
35 46
25 47
5 48
6 49
41 50
42 51
1 52
39 53
14 54...

output:

15734930984

result:

ok single line: '15734930984'

Test #2:

score: 0

Accepted

time: 207ms

memory: 75624kb

input:

499993 461706
1 2
2 3
3 4
1 5
3 6
3 7
7 8
5 9
5 10
7 11
10 12
9 13
13 14
12 15
13 16
15 17
14 18
17 19
16 20
15 21
16 22
17 23
22 24
20 25
23 26
25 27
27 28
28 29
25 30
29 31
30 32
31 33
33 34
33 35
32 36
36 37
35 38
33 39
34 40
35 41
41 42
40 43
42 44
39 45
40 46
41 47
43 48
44 49
46 50
49 51
50 52...

output:

195357165512

result:

ok single line: '195357165512'

Test #3:

score: 0

Accepted

time: 275ms

memory: 75660kb

input:

499993 170472
1 2
1 3
1 4
4 5
5 6
4 7
6 8
5 9
8 10
6 11
6 12
10 13
13 14
11 15
14 16
15 17
14 18
16 19
16 20
17 21
17 22
20 23
19 24
21 25
23 26
22 27
27 28
24 29
24 30
28 31
31 32
30 33
29 34
29 35
35 36
33 37
34 38
36 39
36 40
36 41
41 42
40 43
41 44
39 45
45 46
42 47
47 48
44 49
45 50
46 51
50 52...

output:

65062419628

result:

ok single line: '65062419628'

Test #4:

score: 0

Accepted

time: 207ms

memory: 75632kb

input:

output:

285905307

result:

ok single line: '285905307'

Test #5:

score: 0

Accepted

time: 180ms

memory: 75588kb

input:

output:

98388719

result:

ok single line: '98388719'

Test #6:

score: 0

Accepted

time: 224ms

memory: 75500kb

input:

499999 419261
1 2
2 3
3 4
2 5
3 6
4 7
2 8
6 9
8 10
10 11
10 12
11 13
13 14
12 15
10 16
16 17
14 18
16 19
17 20
16 21
17 22
17 23
20 24
20 25
22 26
26 27
26 28
27 29
24 30
25 31
27 32
30 33
32 34
29 35
34 36
31 37
37 38
38 39
34 40
40 41
37 42
42 43
43 44
40 45
45 46
42 47
42 48
46 49
46 50
45 51
47 ...

output:

174917393258

result:

ok single line: '174917393258'

Test #7:

score: 0

Accepted

time: 200ms

memory: 75680kb

input:

output:

299869724

result:

ok single line: '299869724'

Test #8:

score: 0

Accepted

time: 200ms

memory: 142548kb

input:

499994 469174
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50 51
51 ...

output:

110061651964

result:

ok single line: '110061651964'

Test #9:

score: 0

Accepted

time: 182ms

memory: 142616kb

input:

output:

result:

ok single line: '235984'

Test #10:

score: 0

Accepted

time: 262ms

memory: 142608kb

input:

499990 141264
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50 51
51 ...

output:

9977617584

result:

ok single line: '9977617584'

Test #11:

score: -100

Wrong Answer

time: 260ms

memory: 142572kb

input:

499999 210371
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50 51
51 ...

output:

22128058076

result:

wrong answer 1st lines differ - expected: '22128058078', found: '22128058076'