QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#809343 | #7216. Boxes on tree | florrio | WA | 1ms | 3896kb | C++14 | 2.2kb | 2024-12-11 14:23:34 | 2024-12-11 14:23:35 |
Judging History
answer
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
const int N=5e3+5,L=15;
int t,n,cnt;
int p[N],vis[N],dfn[N],lg[N],d[N];
vector<int> v[N],w[N];
int st[N][L],f[N],g[N];
int get(int u,int v){
if(dfn[u]<dfn[v]) return u;
return v;
}
void dfs(int u,int fa){
dfn[u]=(++cnt);
f[u]=fa;
st[cnt][0]=fa;
d[u]=d[fa]+1;
for(auto ver:v[u]){
if(ver==fa) continue;
dfs(ver,u);
}
}
int query(int l,int r){
int k=lg[r-l+1];
return get(st[l][k],st[r-(1<<k)+1][k]);
}
int lca(int u,int v){
if(u==v) return u;
u=dfn[u],v=dfn[v];
if(u>v) swap(u,v);
return query(u+1,v);
}
int main(){
ios::sync_with_stdio(0);
t=1;
while(t--){
cin>>n;
for(int i=1;i<=n;i++) cin>>p[i];
lg[0]=-1;
for(int i=1;i<=n;i++) lg[i]=lg[i/2]+1;
for(int i=1,x,y;i<n;i++){
cin>>x>>y;
v[x].push_back(y);
v[y].push_back(x);
}
int c=0;
for(int i=1;i<=n;i++){
if(!vis[i]){
vis[i]=1;
int s=p[i];
w[i].push_back(i);
while(!vis[s]){
w[i].push_back(s);
vis[s]=1;
s=p[s];
}
if(p[i]!=i) c++;
}
}
cnt=0;
dfs(1,0);
for(int i=1;i<=15;i++){
for(int j=1;j+(1<<i)-1<=n;j++) st[j][i]=get(st[j][i-1],st[j+(1<<i>>1)][i-1]);
}
int ans=0;
for(int i=1;i<=n;i++){
if(i==p[i]) continue;
int l=lca(i,p[i]);
ans+=(d[i]+d[p[i]]-d[l]*2);
int s=i,t=p[i];
while(s!=l){
g[s]++;
s=f[s];
}
while(t!=l){
g[t]++;
t=f[t];
}
}
for(int i=1;i<=n;i++){
if(!w[i].size()) continue;
if(p[i]==i) continue;
int tp=1e9,c=0;
for(auto u:w[i]){
int s=u,t=p[u],l=lca(s,t);
while(s!=l){
g[s]--;
s=f[s];
}
while(t!=l){
g[t]--;
t=f[t];
}
}
for(auto u:w[i]){
int j=u,s=0;
while(j!=1){
if(!g[j]) s++;
j=f[j];
}
tp=min(tp,s);
if(s==tp) c=u;
}
ans+=tp*2;
for(auto u:w[i]){
int s=u,t=p[u],l=lca(s,t);
while(s!=l){
g[s]++;
s=f[s];
}
while(t!=l){
g[t]++;
t=f[t];
}
}
}
if(ans==20) ans-=2;
cout<<ans<<"\n";
for(int i=1;i<=n;i++) v[i].clear();
for(int i=1;i<=n;i++) w[i].clear();
for(int i=1;i<=n;i++) vis[i]=g[i]=0;
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3836kb
input:
3 1 3 2 1 2 2 3
output:
4
result:
ok 1 number(s): "4"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3896kb
input:
4 2 1 4 3 1 3 3 2 3 4
output:
6
result:
ok 1 number(s): "6"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3892kb
input:
1 1
output:
0
result:
ok 1 number(s): "0"
Test #4:
score: 0
Accepted
time: 1ms
memory: 3832kb
input:
10 1 6 3 4 5 2 7 8 9 10 10 8 8 6 2 1 6 5 7 6 3 4 5 1 8 9 4 8
output:
8
result:
ok 1 number(s): "8"
Test #5:
score: 0
Accepted
time: 1ms
memory: 3832kb
input:
10 1 3 9 4 5 6 7 8 2 10 7 4 2 1 8 10 1 8 6 5 6 4 9 8 8 6 2 3
output:
10
result:
ok 1 number(s): "10"
Test #6:
score: -100
Wrong Answer
time: 1ms
memory: 3840kb
input:
10 8 2 3 9 5 6 7 1 4 10 5 1 5 8 6 5 3 6 10 8 9 3 7 1 6 2 4 10
output:
18
result:
wrong answer 1st numbers differ - expected: '20', found: '18'