QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #388834 | #8134. LCA Counting | cjs | WA | 2ms | 8636kb | C++14 | 2.5kb | 2024-04-13 20:43:47 | 2024-04-13 20:43:47 |
Judging History
answer
#include<bits/stdc++.h>
#define pb push_back
using namespace std;
int read(){
int x=0,f=1;char c;
while(!isdigit(c=getchar()))if(c=='-')f=-1;
while(isdigit(c))x=(x<<1)+(x<<3)+(c&15),c=getchar();
return x*f;
}
const int N=2e5+10;
int n,fa[N],dfn[N],siz[N],num,ans[N],l[N],r[N];
int c[N],f[N];
bool vis[N];
vector<int>e[N],vec,buc0,buc1;
int dep[N];
void dfs(int x){
dep[x]=dep[fa[x]]+1;
dfn[x]=++num,siz[x]=1;
if(!(int)e[x].size())vec.pb(x);
for(int y:e[x]){
dfs(y);
siz[x]+=siz[y];
}
l[x]=dfn[x],r[x]=dfn[x]+siz[x]-1;
}
void add(int x){
for(;x<=n;x+=x&-x)c[x]++;
}
int ask(int x){
int res=0;
for(;x;x-=x&-x)res++;
return res;
}
int calc(int x,int son){
if(vis[x])return 0;
bool flag=0;
for(int y:e[x])if(y!=son){
if(ask(r[y])-ask(l[y]-1)>0){
flag=1;
break;
}
}
if(flag)return x;
return calc(fa[x],x);
}
void dfs2(int x,int v){
if(!(int)e[x].size()){
f[x]=v;
buc1.pb(x);
}
for(int y:e[x])dfs2(y,v);
}
int find(int x){
if(vis[x])return x;
return find(fa[x]);
}
void dfs3(int x,int p){
if(!(int)e[x].size()){
int y=calc(x,0);
if(y)f[x]=y;
else {
f[x]=0;
buc0.pb(x);
}
}
for(int y:e[x])dfs3(y,p);
}
int lca(int x,int y){
if(dep[x]<dep[y])swap(x,y);
while(dep[x]>dep[y])x=fa[x];
if(x==y)return x;
while(x!=y)x=fa[x],y=fa[y];
return x;
}
/*
10
1 1 1 2 2 2 3 3 3
*/
int main()
{
vis[0]=1;
n=read();
for(int i=2;i<=n;i++){
fa[i]=read();
e[fa[i]].pb(i);
}
dfs(1);
int leaf=(int)vec.size();
ans[1]=0,ans[2]=1;int LCA=lca(vec[0],vec.back());
vis[dfn[LCA]]=1;
add(dfn[vec[0]]);
add(dfn[vec.back()]);
for(int j=1;j<leaf-1;j++){
int i=vec[j];
// if(dfn[i]>r[LCA]||dfn[i]<l[LCA]){
// buc0.pb(i);
// continue;
// }
int x=calc(i,0);
if(x){
f[i]=x;
buc1.pb(i);
}
else {
buc0.pb(i);
}
}
for(int i=3;i<=leaf;i++){
while(buc1.size()&&!f[buc1.back()])buc1.pop_back();
if((int)buc1.size()){
int x=buc1.back();
buc1.pop_back();
int p=f[x];
vis[p]=1;
ans[i]=ans[i-1]+1;
while(fa[x]!=p){
int son=x;
x=fa[x];
for(int y:e[x])if(y!=son){
dfs2(y,x);
}
}
add(dfn[x]);
dfs3(p,p);
}
else {
while(buc0.size()&&f[buc0.back()])buc0.pop_back();
ans[i]=ans[i-1];
int x=buc0.back();
buc0.pop_back();
int p=find(x);
while(fa[x]!=p){
int son=x;
x=fa[x];
for(int y:e[x])if(y!=son){
dfs2(y,x);
}
}
add(dfn[x]);
}
}
for(int i=1;i<=leaf;i++)printf("%d ",ans[i]+i);
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 2ms
memory: 8572kb
input:
7 1 1 2 4 2 2
output:
1 3 5 6
result:
ok 4 number(s): "1 3 5 6"
Test #2:
score: 0
Accepted
time: 0ms
memory: 8560kb
input:
10 1 1 2 2 1 1 1 2 4
output:
1 3 5 6 7 8 9
result:
ok 7 numbers
Test #3:
score: 0
Accepted
time: 2ms
memory: 8552kb
input:
10 1 2 2 4 5 6 1 2 4
output:
1 3 5 7 8
result:
ok 5 number(s): "1 3 5 7 8"
Test #4:
score: 0
Accepted
time: 0ms
memory: 8496kb
input:
10 1 2 3 3 3 5 6 4 9
output:
1 3 4
result:
ok 3 number(s): "1 3 4"
Test #5:
score: -100
Wrong Answer
time: 0ms
memory: 8636kb
input:
1000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 2 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 4 1 2 2 1 1 1 1 2 1 1 1 1 2 2 1 1 1 1 1 6 3 1 1 1 2 2 1 1 2 1 2 1 3 1 2 1 1 2 1 1 1 1 1 1 1 4 1 5 1 1 1 1 1 2 1 1 2 1 2 1 2 5 3 1 3 1 1 2 1 2 1 1 3 2 1 6 2 1 2 5 1 1 1 3 2 1 2 1 1 1 1 1...
output:
1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 12...
result:
wrong answer 5th numbers differ - expected: '8', found: '9'