QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#603057 | #8720. BFS 序 0 | lllei# | WA | 584ms | 96576kb | C++20 | 5.1kb | 2024-10-01 14:26:50 | 2024-10-01 14:26:51 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 10;
struct seg {
int l, r;
};
seg merge(seg t1, seg t2) {
t1.l = min(t1.l, t2.l);
t1.r = max(t1.r, t2.r);
return t1;
}
bool involve(seg t1, seg t2) {
if (t1.l > t2.r || t2.l > t1.r)
return false;
return true;
}
struct s {
map<int, seg> p;
vector<int> lay;
int siz;
} node[N];
int belon[N];
bool check(int t1, int t2) {
int flag2 = 0;
int tmp = node[t2].lay.size();
for (int i = 0; i < tmp; i++) {
int now = node[t2].lay[i];
if (node[t1].p.contains(now)) {
seg tmp1 = node[t1].p[now], tmp2 = node[t2].p[now];
if (involve(tmp1, tmp2))
return false;
if (tmp1.l < tmp2.l) {
if (flag2) {
if (flag2 == 2)
return false;
} else
flag2 = 1;
} else {
if (flag2) {
if (flag2 == 1)
return false;
} else
flag2 = 2;
}
}
}
return true;
}
bool mergenode(int t1, int t2) { // t1<-t2
int tmp1 = belon[t1], tmp2 = belon[t2];
if (node[tmp1].siz < node[tmp2].siz)
swap(tmp1, tmp2);
belon[t1] = tmp1;
bool flag1 = check(tmp1, tmp2);
int tmp = node[tmp2].lay.size();
for (int i = 0; i < tmp; i++) {
int now = node[tmp2].lay[i];
if (!node[tmp1].p.contains(now)) {
node[tmp1].p[now] = node[tmp2].p[now];
node[tmp1].lay.push_back(now);
} else
node[tmp1].p[now] = merge(node[tmp1].p[now], node[tmp2].p[now]);
}
return flag1;
}
int n, fa[N], m, q, pa[N][22];
int dep[N];
int id[N];
int lca(int t1, int t2) {
if (dep[t1] > dep[t2])
swap(t1, t2);
for (int i = 20; i >= 0; i--)
if (dep[pa[t2][i]] >= dep[t1])
t2 = pa[t2][i];
if (t1 == t2)
return t1;
for (int i = 20; i >= 0; i--)
if (pa[t1][i] != pa[t2][i]) {
t1 = pa[t1][i];
t2 = pa[t2][i];
}
return pa[t1][0];
}
vector<int> son[N];
int dfn[N], tme = 0;
int faa[N]; // xushu
void dfs(int now) {
dfn[now] = ++tme;
int tmp = son[now].size();
for (int i = 0; i < tmp; i++)
dfs(son[now][i]);
return;
}
int bfn[N], rak[N];
vector<int> b;
bool ss(int t1, int t2) {
return dfn[t1] < dfn[t2];
}
int sonnum[N];
int main() {
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(0);
cin >> n;
for (int i = 2; i <= n; i++) {
cin >> fa[i];
son[fa[i]].push_back(i);
}
dfs(1);
for (int i = 1; i <= n; i++)
pa[i][0] = fa[i];
for (int i = 1; i <= 20; i++)
for (int j = 1; j <= n; j++)
pa[j][i] = pa[pa[j][i - 1]][i - 1];
dep[1] = 1;
for (int i = 2; i <= n; i++)
dep[i] = dep[fa[i]] + 1;
cin >> q;
while (q--) {
cin >> m;
for (int i = 1; i <= m; i++) {
cin >> bfn[i];
rak[bfn[i]] = i;
id[i] = bfn[i];
}
sort(id + 1, id + m + 1, ss);
bool flag = true;
for (int i = 2; i <= m; i++)
if (dep[bfn[i]] < dep[bfn[i - 1]]) {
flag = false;
break;
}
for (int i = 1; i < m; i++) {
int now = lca(id[i], id[i + 1]);
node[now].p.clear();
node[now].siz = 0;
node[now].lay.clear();
belon[now] = now;
}
for (int i = 1; i <= m; i++) {
node[bfn[i]].p.clear();
node[bfn[i]].lay.clear();
seg tmp1;
tmp1.l = tmp1.r = i;
node[bfn[i]].p[dep[i]] = tmp1;
node[bfn[i]].siz = 1;
belon[bfn[i]] = bfn[i];
node[bfn[i]].lay.push_back(dep[bfn[i]]);
}
b.clear();
b.push_back(1);
for (int i = 1; i <= m; i++) {
b.push_back(id[i]);
if (i != m)
b.push_back(lca(id[i], id[i + 1]));
}
b.erase(unique(b.begin(), b.end()), b.end());
int tmp = b.size();
for (int i = 0; i < tmp; i++)
sonnum[b[i]] = 0;
for (int i = 0; i < tmp - 1; i++) {
int lcaa = lca(b[i], b[i + 1]);
faa[b[i + 1]] = lcaa;
sonnum[lcaa]++;
}
queue<int> q;
for (int i = 0; i < tmp; i++)
if (sonnum[b[i]] == 0)
q.push(b[i]);
while (!q.empty()) {
int now = q.front();
q.pop();
if (!mergenode(now, faa[now]))
flag = false;
sonnum[faa[now]]--;
if (sonnum[faa[now]] == 0)
q.push(faa[now]);
}
if (flag)
cout << "Yes\n";
else
cout << "No\n";
}
return 0;
}
/*
6
1 1 3 2 4
10
4 3 6 2 5
1 4
3 2 4 5
5 2 5 4 6 3
3 1 4 2
3 5 6 3
5 4 5 2 6 1
4 4 3 2 5
4 4 6 2 3
3 3 2 6
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 38968kb
input:
6 1 1 3 2 4 10 4 3 6 2 5 1 4 3 2 4 5 5 2 5 4 6 3 3 1 4 2 3 5 6 3 5 4 5 2 6 1 4 4 3 2 5 4 4 6 2 3 3 3 2 6
output:
No Yes Yes No No No No No No Yes
result:
ok 10 token(s): yes count is 3, no count is 7
Test #2:
score: -100
Wrong Answer
time: 584ms
memory: 96576kb
input:
300000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...
output:
Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes ...
result:
wrong answer expected NO, found YES [1st token]