QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#603099 | #8720. BFS 序 0 | lllei# | WA | 907ms | 96236kb | C++20 | 5.6kb | 2024-10-01 14:42:02 | 2024-10-01 14:42:04 |
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;
}
struct cmp
{
bool operator () (int tt1,int tt2) {
int t1=belon[tt1],t2=belon[tt2];
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 (tmp1.l < tmp2.l) {
return true;
}
if(tmp1.l>tmp2.l) return false;
}
}
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[bfn[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]++;
}
priority_queue<int,vector<int>,cmp> q;
for (int i = 0; i < tmp; i++)
if (sonnum[b[i]] == 0)
q.push(b[i]);
while (!q.empty()) {
int now = q.top();
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
*/
詳細信息
Test #1:
score: 100
Accepted
time: 3ms
memory: 39536kb
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: 907ms
memory: 96236kb
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]