QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#95782 | #5580. Branch Manager | __# | WA | 1392ms | 35932kb | C++14 | 3.3kb | 2023-04-11 21:41:14 | 2023-04-11 21:41:18 |
Judging History
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'