QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#95782#5580. Branch Manager__#WA 1392ms35932kbC++143.3kb2023-04-11 21:41:142023-04-11 21:41:18

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-04-11 21:41:18]
  • 评测
  • 测评结果:WA
  • 用时:1392ms
  • 内存:35932kb
  • [2023-04-11 21:41:14]
  • 提交

answer

#pragma GCC optimize("Ofast")
#pragma GCC optimize("O3")

#include <bits/stdc++.h>
using namespace std;

#define el '\n'
#define F first
#define S second

typedef long long ll;
typedef long double ld;

bool multipleTestCases = 0, sublime = 0;
const int N = 2e5 + 5, INF = 1e9 + 5, mod = 1e9 + 7, LOG = 22, SQ = 500;

int n, q, qu[N], in[N], out[N], timer;
vector<int> g[N];
vector<pair<int, int>> ord;
bool fail;

void dfsFlat(int node) {
    in[node] = timer++;
    ord.push_back({node, 1});

    for (auto &i : g[node]) {
        dfsFlat(i);
    }

    out[node] = timer++;
    ord.push_back({node, 2});
}

struct SegmentTree{
    vector<int> tree;
    int neutral;

    SegmentTree(){}

    SegmentTree(int sz){
        tree.assign(4 * sz, -INF);
        neutral = -INF;
    }

    int merge(int &u, int &v){
        return max(u, v);
    }

    void set(int node, int start, int end, int idx, int val){
        if(start == end)
            return tree[node] = val, void();

        int m = (start + end) >> 1;

        if(idx <= m)
            set(2 * node, start, m, idx, val);
        else
            set(2 * node + 1, m + 1, end, idx, val);

        tree[node] = merge(tree[2 * node], tree[2 * node + 1]);
    }

    ll query(int node, int start, int end, int left, int right){
        if (right < left) {
            return neutral;
        }
        if(end < left or start > right)
            return neutral;

        if(left <= start and end <= right)
            return tree[node];

        int m = (start + end) >> 1;
        int l = query(2 * node, start, m, left, right);
        int r = query(2 * node + 1, m + 1, end, left, right);
        return merge(l, r);
    }
} st;

void dfs(int node) {
    if (fail) return;

    vector<int> v;

    for (auto &i : g[node]) {
        int val = st.query(1, 1, 2 * n, in[i], out[i]);

        if (val != -INF) {
            v.push_back(val);
        }
    }

    fail |= !is_sorted(v.begin(), v.end());

    if (fail) return;

    for (auto &i : g[node]) {
        dfs(i);
    }
}

bool valid(int m) {
    st = SegmentTree(2 * n);
    fail = 0;

    for (int i = 1; i <= m; i++) {
        st.set(1, 1, 2 * n, in[qu[i]], i);
    }

    dfs(1);

    return (fail ? 0 : 1);
}

void doWork() {
    cin >> n >> q;

    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
    }

    for (int i = 1; i <= n; i++) {
        sort(g[i].begin(), g[i].end());
    }

    dfsFlat(1);

    for (int i = 1; i <= q; i++) {
        cin >> qu[i];
    }

    int s = 0, e = q, m, ans = 0;

    while (s <= e) {
        m = (s + e) >> 1;

        if (valid(m)) {
            ans = m;
            s = m + 1;
        }
        else {
            e = m - 1;
        }
    }

    cout << ans << el;
}
signed main() {
#ifdef ONLINE_JUDGE
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#endif
#ifndef ONLINE_JUDGE
    if (sublime) {
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    }
#endif
    int tests = 1;
    if (multipleTestCases) {
        cin >> tests;
    }
    for (int tc = 1; tc <= tests; tc++) {
        doWork();
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 5ms
memory: 10280kb

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: 9524kb

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: 4ms
memory: 9312kb

input:

2 2
1 2
2
2

output:

2

result:

ok single line: '2'

Test #4:

score: 0
Accepted
time: 326ms
memory: 35932kb

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: 1392ms
memory: 30684kb

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: 90ms
memory: 10824kb

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: -100
Wrong Answer
time: 1ms
memory: 8596kb

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:

67

result:

wrong answer 1st lines differ - expected: '11', found: '67'