QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#127534#5580. Branch Managerbatrr#AC ✓435ms45816kbC++172.1kb2023-07-19 19:25:372023-07-19 19:25:39

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-19 19:25:39]
  • 评测
  • 测评结果:AC
  • 用时:435ms
  • 内存:45816kb
  • [2023-07-19 19:25:37]
  • 提交

answer

#include <bits/stdc++.h>

#define f first
#define s second
#define pb push_back
#define mp make_pair

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;

const int N = 300500, inf = 1e9, mod = 998244353;
const ll INF = 1e18;

int sum(int a, int b) {
    a += b;
    if (a >= mod)
        a -= mod;
    return a;
}

int sub(int a, int b) {
    a -= b;
    if (a < 0)
        a += mod;
    return a;
}

int mult(int a, int b) {
    return 1ll * a * b % mod;
}

int bp(int a, int b) {
    int res = 1;
    while (b) {
        if (b & 1)
            res = mult(res, a);
        a = mult(a, a);
        b >>= 1;
    }
    return res;
}

int inv(int x) {
    return bp(x, mod - 2);
}

int n, m, a[N];
vector<int> g[N], gq[N];
bool OK;

pii dp[N];

void dfs(int v){
    sort(g[v].begin(), g[v].end());
    int x = -inf;
    dp[v].f = inf;
    dp[v].s = -inf;
    for(auto to : g[v]){
        dfs(to);

        if(dp[to].f == inf)
            continue;

        if(dp[to].f < x)
            OK = 0;
        x = dp[to].s;
        dp[v].f = min(dp[v].f, dp[to].f);
        dp[v].s = max(dp[v].s, dp[to].s);
    }

    for(auto x : gq[v]){
        dp[v].f = min(dp[v].f, x);
        dp[v].s = max(dp[v].s, x);
    }
}
bool check(int k) {
    for(int i = 1; i <= n; i++)
        gq[i].clear();
    for (int i = 0; i < k; i++)
        gq[a[i]].pb(i);
    OK = 1;
    dfs(1);
    return OK;
}

void solve() {
    cin >> n >> m;
    for (int i = 0; i < n - 1; i++) {
        int a, b;
        cin >> a >> b;
        g[a].pb(b);
    }
    for (int i = 0; i < m; i++)
        cin >> a[i];
    int l = 0, r = m;
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (check(mid))
            l = mid + 1;
        else
            r = mid - 1;
    }
    cout << l - 1 << endl;
}

int main() {
#ifdef DEBUG
    freopen("input.txt", "r", stdin);
#endif
    ios_base::sync_with_stdio(false);
    int t = 1;
//    cin >> t;
    for (int i = 1; i <= t; i++) {
//        cout << "Case #" << i << endl;
        solve();
    }
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 19916kb

input:

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

output:

5

result:

ok single line: '5'

Test #2:

score: 0
Accepted
time: 5ms
memory: 18356kb

input:

4 4
1 2
1 3
1 4
3
2
3
4

output:

1

result:

ok single line: '1'

Test #3:

score: 0
Accepted
time: 5ms
memory: 19864kb

input:

2 2
1 2
2
2

output:

2

result:

ok single line: '2'

Test #4:

score: 0
Accepted
time: 209ms
memory: 26060kb

input:

200000 200000
161672 172858
146306 146322
61159 61510
140802 145171
194221 195447
73888 80278
77016 77115
1382 1417
186221 195091
78442 78451
171750 172141
147707 151432
182664 182798
143183 147414
156646 162546
6630 6706
18452 18519
99764 99811
153419 153707
125659 129068
179317 185954
13947 14278
...

output:

3563

result:

ok single line: '3563'

Test #5:

score: 0
Accepted
time: 261ms
memory: 27292kb

input:

200000 200000
73559 73695
138868 139314
169919 172147
3308 3348
35604 35605
180658 181072
114345 115218
146174 146449
21102 21786
107951 109513
9726 9970
50 51
154991 159020
49941 50155
4670 4671
90651 90653
76212 81669
173486 173539
143322 143389
191619 193955
14951 15097
136371 141417
59383 60502
...

output:

200000

result:

ok single line: '200000'

Test #6:

score: 0
Accepted
time: 23ms
memory: 20716kb

input:

20000 20000
2163 2201
12429 12586
3232 3520
15314 15325
802 804
4746 5448
1061 1088
13374 13407
13566 14044
19080 19290
16461 16914
11323 11324
1594 1595
3588 3980
17217 19232
1828 1941
10180 10195
3112 4898
12823 13622
16020 16093
2773 2892
12885 13851
18980 19043
10476 10493
9902 10012
15286 15440...

output:

20000

result:

ok single line: '20000'

Test #7:

score: 0
Accepted
time: 5ms
memory: 18564kb

input:

34 392
1 25
1 9
1 21
2 27
1 7
1 20
2 11
6 28
3 33
1 22
1 8
1 10
1 5
1 23
1 14
3 30
2 6
1 12
1 15
1 19
1 18
1 31
1 2
1 16
2 26
1 3
1 4
5 24
10 32
3 34
1 13
2 17
1 29
6
6
28
28
28
28
28
28
2
11
11
28
28
28
28
28
28
28
28
28
2
11
11
11
11
11
11
11
11
11
11
11
11
11
11
2
17
17
17
17
17
17
17
17
17
17
17...

output:

11

result:

ok single line: '11'

Test #8:

score: 0
Accepted
time: 4ms
memory: 17760kb

input:

3 5
1 2
2 3
2
3
2
2
3

output:

5

result:

ok single line: '5'

Test #9:

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

input:

198 188
129 142
82 83
31 32
93 98
5 6
86 87
71 75
78 79
98 102
57 66
45 52
90 91
142 179
151 158
172 183
15 18
189 194
159 168
148 153
18 21
86 141
166 195
2 4
38 41
111 112
87 127
13 15
88 94
133 174
105 106
3 5
87 97
73 80
121 129
23 25
43 70
127 166
129 143
56 65
39 42
56 61
174 177
2 3
37 54
70 ...

output:

188

result:

ok single line: '188'

Test #10:

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

input:

200 187
88 89
137 138
58 59
19 20
99 100
127 128
48 49
173 174
17 18
75 76
136 137
128 129
100 101
97 98
51 52
4 5
73 74
6 7
138 139
187 188
151 152
37 38
43 44
23 24
120 121
196 197
98 99
42 43
109 110
89 90
130 131
125 126
62 63
106 107
78 79
190 191
93 94
168 169
161 162
158 159
36 37
61 62
165 1...

output:

187

result:

ok single line: '187'

Test #11:

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

input:

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

output:

2

result:

ok single line: '2'

Test #12:

score: 0
Accepted
time: 141ms
memory: 24828kb

input:

200000 200000
1 99604
1 92192
1 76766
1 86883
1 77992
1 107401
1 63372
1 162116
1 120232
1 37089
1 93172
1 34383
1 196526
1 25633
1 177265
1 159035
1 149616
1 17433
1 39492
1 671
1 24966
1 55858
1 85586
1 28298
1 4970
1 172349
1 139382
1 121034
1 131345
1 184645
1 68952
1 29195
1 129941
1 83951
1 17...

output:

200000

result:

ok single line: '200000'

Test #13:

score: 0
Accepted
time: 101ms
memory: 23124kb

input:

200000 200000
1 79738
1 45523
1 56820
1 102764
1 147970
1 111851
1 1365
1 63366
1 29471
1 147031
1 169622
1 176480
1 111848
1 43158
1 98829
1 112119
1 159407
1 102889
1 162277
1 141904
1 1832
1 105887
1 164798
1 51504
1 72907
1 159194
1 23839
1 165104
1 178506
1 54064
1 199386
1 137629
1 137660
1 41...

output:

31596

result:

ok single line: '31596'

Test #14:

score: 0
Accepted
time: 435ms
memory: 45816kb

input:

200000 200000
28491 28492
608 609
175084 175085
63627 63628
42437 42438
34167 34168
94439 94440
65456 65457
12245 12246
78262 78263
39341 39342
168132 168133
21429 21430
42212 42213
84000 84001
25125 25126
104132 104133
129301 129302
48878 48879
107778 107779
192433 192434
105565 105566
40250 40251
...

output:

200000

result:

ok single line: '200000'

Test #15:

score: 0
Accepted
time: 426ms
memory: 45492kb

input:

200000 200000
168459 168460
15232 15233
192243 192244
130078 130079
65195 65196
37807 37808
109352 109353
17134 17135
20465 20466
28749 28750
141730 141731
97789 97790
154131 154132
175321 175322
7161 7162
106516 106517
62592 62593
95590 95591
65225 65226
112792 112793
113385 113386
90609 90610
2361...

output:

200000

result:

ok single line: '200000'

Test #16:

score: 0
Accepted
time: 233ms
memory: 34076kb

input:

200000 200000
62244 123458
39383 154122
46805 142116
71577 71578
6372 6373
68089 68090
31520 31521
13912 13913
22548 22549
4640 198274
64215 64216
88180 88181
37934 166771
71921 71922
17032 17033
76272 76273
47840 133692
1343 1344
16085 16086
77340 77341
88700 103980
71529 71530
62541 62542
35671 35...

output:

200000

result:

ok single line: '200000'

Test #17:

score: 0
Accepted
time: 188ms
memory: 34208kb

input:

200000 200000
62242 62243
44272 108109
49004 49005
14401 14402
63306 63307
89216 104665
19599 156425
54608 54609
46437 46438
55382 142176
8754 8755
10855 187941
36963 36964
68678 68679
1981 1982
66883 66884
76331 187997
32781 128583
61109 61110
78094 78095
53074 188371
40251 40252
32361 178425
31685...

output:

140902

result:

ok single line: '140902'

Test #18:

score: 0
Accepted
time: 106ms
memory: 23564kb

input:

200000 200000
3516 104976
1569 142576
646 36086
3818 44813
3303 43028
1202 156768
3697 67333
1739 174091
353 81325
3194 114577
1324 117981
1675 13872
3562 86276
733 37365
836 81804
2736 33189
2965 179808
2832 106765
1204 111744
1554 164782
1082 83661
125 84986
1309 68817
634 168972
2341 151930
1410 ...

output:

200000

result:

ok single line: '200000'

Test #19:

score: 0
Accepted
time: 100ms
memory: 24108kb

input:

200000 200000
1236 1237
5736 55984
3403 155825
3637 122025
8960 133788
7369 150928
3073 3074
6412 157336
5158 144490
5034 108204
3478 3479
8796 52783
8678 184693
812 169399
5456 169518
3556 31452
1507 74151
6634 17726
1901 188183
7633 25752
9094 146439
1732 161061
392 34261
2727 15276
9270 89725
826...

output:

143317

result:

ok single line: '143317'