QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#294258#392. Patrolkiller100 ✓28ms34036kbC++143.8kb2023-12-30 10:58:502023-12-30 10:58:51

Judging History

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

  • [2023-12-30 10:58:51]
  • 评测
  • 测评结果：100
  • 用时：28ms
  • 内存：34036kb
查看
  • [2023-12-30 10:58:50]
  • 提交

answer

    #include <bits/stdc++.h>
    #define ll long long
    #define pb push_back
    #define task "test"
    #define pll pair<ll, ll>
    #define pii pair<pll, ll>
    #define fi first
    #define se second

    using namespace std;
    const ll mod =  998244353;
    const ll N = 3e5+5;
    const int base = 400;
    int n, m, t, k, T, ans0, ans1, ans2, c[N], a[N], b[N], dp[N][3];
    vector<int> adj[N], kq, val[N];

    string s[N], ss;
    ll pw(ll k, ll n)
    {
        ll total = 1;
        for(; n; n >>= 1)
        {
            if(n & 1)total = total * k % mod;
            k = k * k % mod;
        }
        return total;
    }

    void dfs(int u, int p)
    {
        dp[u][0] = 0;
        dp[u][1] = 0;
        dp[u][2] = 0;
        int mx1 = 0, mx2 = 0;
        vector<int> cur;
        for(int v: adj[u]){
            if(v == p)continue;
            dfs(v, u);
            dp[u][0] = max(dp[u][0], dp[v][0]+1);
            dp[u][1] = max(dp[u][1], dp[v][1]+1);
            dp[u][2] = max(dp[u][2], dp[v][2]);
            cur.pb(dp[v][0]+1);
            if(dp[v][2] > mx1){
                mx2 = mx1;
                mx1 = dp[v][2];
            }
            else if(dp[v][2] > mx2)mx2 = dp[v][2];
        }
        ans2 = max(ans2, mx1+mx2);
        // cout << u <<" "<<mx1<<" "<<mx2<<'\n';
        // for(int v: adj[u])if(v != p)cout <<v<<" "<< dp[v][2] <<" ";
        // cout << '\n';
        int sz = adj[u].size();
        int sum = 0;
        for(int i = 0; i < sz; i ++){
            int v = adj[u][i];
            b[i] = 0;
            if(v != p)b[i] = dp[v][0]+1;
            if(i)b[i] = max(b[i], b[i-1]);
            if(v == p)continue;
            if(i)sum = max(sum, b[i-1]+dp[v][0]+1);
            else sum = max(sum, dp[v][0]+1);
        }    
        ans0 = max(ans0, sum);
        dp[u][2] = max(dp[u][2], sum);
        
        if(k == 2){
            for(int i = 0; i < sz; i ++){
                int v = adj[u][i];
                b[i] = 0;
                if(v != p)b[i] = dp[v][0]+1;
                if(i)b[i] = max(b[i], b[i-1]);
                if(v == p)continue;
                dp[u][1] = max(dp[u][1], dp[v][2]+b[i-1]);
                if(i)ans1 = max(ans1, b[i-1]+max(dp[v][1]+1, dp[v][2]));
                else ans1 = max(ans1, max(dp[v][1]+1, dp[v][2]));
            }         
            c[sz] = 0;
            for(int i = sz-1; i >= 0; i --){
                int v = adj[u][i];
                c[i] = 0;
                if(v != p)c[i] = dp[v][0]+1;
                c[i] = max(c[i], c[i+1]);
                if(v == p)continue;
                dp[u][1] = max(dp[u][1], dp[v][2]+c[i+1]);
                ans1 = max(ans1, c[i+1]+max(dp[v][1]+1, dp[v][2]));
                if(i)ans1 = max(ans1, c[i+1]+b[i-1]+ dp[v][2]);
            }  
            sort(cur.rbegin(), cur.rend());
            sum = 0;
            for(int i = 0; i < min(3, (int)cur.size()); i ++)sum += cur[i];
            dp[u][1] = max(dp[u][1], sum);
            ans1 = max(ans1, sum);
            if(cur.size()>3)ans1=max(ans1,sum+cur[3]);
        }

    }
    void sol()
    {
        cin >> n >> k;
        for(int i = 1; i < n; i ++)
        {
            int x, y;
            cin >> x >> y;
            adj[x].pb(y);
            adj[y].pb(x);
        }
        dfs(1, 0);
        ans0 = 2*(n-1)-ans0+1;
        // cout << ans1 <<" "<<ans2<<'\n';
        if(k == 2)
            ans0 = 2*(n-1)-max(ans1,ans2)+2;
        cout << ans0;

    }
    int main()
    {
        if(fopen(task".inp", "r"))
        {
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
        }
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
        int ntest = 1;
        //cin >> ntest;
        while(ntest -- > 0)
        sol();
    }
Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 3.33333
Accepted
time: 3ms
memory: 26892kb

input:

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

output:

15

result:

ok single line: '15'

Test #2:

score: 3.33333
Accepted
time: 3ms
memory: 26932kb

input:

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

output:

385

result:

ok single line: '385'

Test #3:

score: 3.33333
Accepted
time: 0ms
memory: 26996kb

input:

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

output:

1831

result:

ok single line: '1831'

Test #4:

score: 3.33333
Accepted
time: 4ms
memory: 27104kb

input:

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

output:

9965

result:

ok single line: '9965'

Test #5:

score: 3.33333
Accepted
time: 8ms
memory: 27844kb

input:

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

output:

39961

result:

ok single line: '39961'

Test #6:

score: 3.33333
Accepted
time: 25ms
memory: 31372kb

input:

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

output:

199955

result:

ok single line: '199955'

Test #7:

score: 3.33333
Accepted
time: 3ms
memory: 27588kb

input:

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

output:

18340

result:

ok single line: '18340'

Test #8:

score: 3.33333
Accepted
time: 17ms
memory: 30480kb

input:

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

output:

91709

result:

ok single line: '91709'

Test #9:

score: 3.33333
Accepted
time: 22ms
memory: 33984kb

input:

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

output:

183360

result:

ok single line: '183360'

Test #10:

score: 3.33333
Accepted
time: 0ms
memory: 26940kb

input:

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

output:

28

result:

ok single line: '28'

Test #11:

score: 3.33333
Accepted
time: 0ms
memory: 26940kb

input:

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

output:

175

result:

ok single line: '175'

Test #12:

score: 3.33333
Accepted
time: 3ms
memory: 27016kb

input:

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

output:

1953

result:

ok single line: '1953'

Test #13:

score: 3.33333
Accepted
time: 6ms
memory: 27340kb

input:

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

output:

19934

result:

ok single line: '19934'

Test #14:

score: 3.33333
Accepted
time: 10ms
memory: 27448kb

input:

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

output:

19930

result:

ok single line: '19930'

Test #15:

score: 3.33333
Accepted
time: 16ms
memory: 29156kb

input:

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

output:

99922

result:

ok single line: '99922'

Test #16:

score: 3.33333
Accepted
time: 28ms
memory: 31416kb

input:

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

output:

199910

result:

ok single line: '199910'

Test #17:

score: 3.33333
Accepted
time: 0ms
memory: 26972kb

input:

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

output:

1798

result:

ok single line: '1798'

Test #18:

score: 3.33333
Accepted
time: 3ms
memory: 27024kb

input:

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

output:

3615

result:

ok single line: '3615'

Test #19:

score: 3.33333
Accepted
time: 6ms
memory: 27660kb

input:

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

output:

18240

result:

ok single line: '18240'

Test #20:

score: 3.33333
Accepted
time: 7ms
memory: 30448kb

input:

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

output:

91573

result:

ok single line: '91573'

Test #21:

score: 3.33333
Accepted
time: 21ms
memory: 32672kb

input:

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

output:

146479

result:

ok single line: '146479'

Test #22:

score: 3.33333
Accepted
time: 21ms
memory: 34036kb

input:

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

output:

183232

result:

ok single line: '183232'

Test #23:

score: 3.33333
Accepted
time: 4ms
memory: 27336kb

input:

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

output:

19495

result:

ok single line: '19495'

Test #24:

score: 3.33333
Accepted
time: 3ms
memory: 27384kb

input:

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

output:

18913

result:

ok single line: '18913'

Test #25:

score: 3.33333
Accepted
time: 8ms
memory: 29236kb

input:

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

output:

98142

result:

ok single line: '98142'

Test #26:

score: 3.33333
Accepted
time: 11ms
memory: 29428kb

input:

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

output:

99957

result:

ok single line: '99957'

Test #27:

score: 3.33333
Accepted
time: 8ms
memory: 29244kb

input:

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

output:

99970

result:

ok single line: '99970'

Test #28:

score: 3.33333
Accepted
time: 15ms
memory: 31592kb

input:

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

output:

199971

result:

ok single line: '199971'

Test #29:

score: 3.33333
Accepted
time: 19ms
memory: 31728kb

input:

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

output:

199949

result:

ok single line: '199949'

Test #30:

score: 3.33333
Accepted
time: 19ms
memory: 31308kb

input:

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

output:

199976

result:

ok single line: '199976'
English 繁體中文 简体中文

Server Time: 2024-12-04 06:22:45 | OpenSource Project