QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#417270 | #8720. BFS 序 0 | hyfcabbyblue | WA | 254ms | 63256kb | C++14 | 3.6kb | 2024-05-22 16:53:23 | 2024-05-22 16:53:23 |
Judging History
answer
# include <bits/stdc++.h>
# define int long long
using namespace std;
const int N = 5e5 + 5;
const int inf = 4e18;
int n, q;
int fa[N];
int dfn[N];
int tot;
int siz[N];
int dep[N];
vector <int> e[N];
int a[N];
vector <int> g[N];
void dfs(int u)
{
siz[u] = 1;
dfn[u] = ++tot;
dep[u] = dep[fa[u]] + 1;
for(int i = 0; i < e[u].size(); i++)
{
int v = e[u][i];
dfs(v);
siz[u] += siz[v];
}
}
struct segmentTr
{
int cnt;
int sum[N * 4];
int lazy[N * 4];
int lson[N * 4];
int rson[N * 4];
void clear()
{
cnt = 1;
lazy[1] = inf;
sum[1] = 0;
lson[1] = 0;
rson[1] = 0;
}
int newnode(int &x)
{
if(x) return x;
x = ++cnt;
lazy[x] = inf;
lson[x] = rson[x] = 0;
sum[x] = 0;
return x;
}
void update(int i, int l, int r, int c)
{
sum[i] = (r - l + 1) * c;
lazy[i] = c;
}
void down(int i, int l, int r)
{
if(lazy[i] == inf)
{
return;
}
int mid = l + r >> 1;
update(newnode(lson[i]), l, mid, lazy[i]);
update(newnode(rson[i]), mid + 1, r, lazy[i]);
lazy[i] = inf;
}
void pushup(int i)
{
sum[i] = sum[lson[i]] + sum[rson[i]];
}
void modify(int i, int l, int r, int L, int R, int cov)
{
if(R < l || r < L)
{
return;
}
if(L <= l && r <= R)
{
update(i, l, r, cov);
return;
}
down(i, l, r);
int mid = l + r >> 1;
modify(newnode(lson[i]), l, mid, L, R, cov);
modify(newnode(rson[i]), mid + 1, r, L, R , cov);
pushup(i);
}
int query(int i, int l, int r, int x)
{
if(l == r)
{
return sum[i];
}
down(i, l, r);
int mid = l + r >> 1;
if(x <= mid) return query(newnode(lson[i]), l, mid, x);
return query(newnode(rson[i]), mid + 1, r, x);
}
}Tr;
void check()
{
Tr.clear();
int m;
cin >> m;
map <int, bool> v;
for(int i = 1; i <= m; i++)
{
cin >> a[i];
}
for(int i = 1; i <= m; i++)
{
if(a[i] < 1|| a[i] > n)
{
cout << "No" << endl;
return;
}
}
for(int i = 1; i <= m; i++)
{
if(v[a[i]])
{
cout << "No" << endl;
return;
}
v[a[i]] = 1;
}
for(int i = 1; i <= m; i++)
{
if(i > 1 && dep[a[i]] < dep[a[i - 1]])
{
cout << "No" << endl;
return;
}
}
for(int i = 1; i <= m; i++)
{
g[dep[a[i]]].push_back(a[i]);
}
bool flag = 1;
int w = 0;
for(int i = 1; i <= n; i++)
{
int precov = 0;
int cov;
for(int j = 0; j < g[i].size(); j++)
{
int now = g[i][j];
cov = Tr.query(1, 1, n, dfn[now]);
if(precov && cov)
{
if(precov > cov)
{
flag = 0;
}
}
// cout<<precov<<" "<<now<<" "<<cov<<" "<<i<<endl;
if(flag == 0) break;
if(cov) precov = cov;
// cout<<"*"<<precov<<" "<<cov<<endl;
}
if(flag == 0) break;
for(int j = 0; j < g[i].size(); j++)
{
++w;
int now = g[i][j];
Tr.modify(1, 1, n, dfn[now], dfn[now] + siz[now] - 1, w);
}
}
if(flag)
{
cout << "Yes" << endl;
}
else
{
cout << "No" << endl;
}
for(int i = 1; i <= m; i++)
{
g[dep[i]].clear();
}
}
signed main()
{
cin >> n;
for(int i = 2; i <= n; i++)
{
cin >> fa[i];
e[fa[i]].push_back(i);
}
bool flag = 0;
for(int i = 2; i <= n; i++)
{
if(fa[i] != 1) flag = 1;
}
if(!flag)
{
cout<<1;
}
dfs(1);
// for(int i = 1; i <= n; i++)
// {
// cout << dfn[i] << " " << siz[i]<<endl;
// }
cin >> q;
while(q--)
{
check();
}
return 0;
}
/*
6
1 1 3 2 4
12
4 3 2 4 5
4 3 2 5 4
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: 0ms
memory: 40448kb
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: 254ms
memory: 63256kb
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:
No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No ...
result:
wrong answer expected YES, found NO [2nd token]