QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#382498 | #3748. 买一送一 | 秦始皇派蒙恬还原神舟十二 (Jiancong Wen, Chu Jin, Zekai Zhang) | AC ✓ | 151ms | 23580kb | C++17 | 1.7kb | 2024-04-08 15:33:37 | 2024-04-08 15:33:37 |
Judging History
answer
#include<iostream>
#include<string.h>
#include<stdio.h>
#include<map>
#include<vector>
#include<queue>
#include<stack>
#include<math.h>
#include<set>
#include<deque>
#include<unordered_map>
#include<algorithm>
#define int long long
using namespace std;
typedef pair<int,int>PII;
const int N=1e5+10,M=5e2+10;
vector<int>v[N];
int w[N];
int ans[N];
int st[N];//出现次数
int nu[N];
void dfs(int no,int la,int num){
// cout<<no<<" "<<la<<" "<<num<<"!!!!\n";
if(st[w[no]]!=0){
if(st[w[no]]==1){
// cout<<"***\n";
// cout<<nu[w[no]]<<"###\n";
ans[no]=ans[la]+num-nu[w[no]]+1;
int pp=v[no].size();
for(int i=0;i<pp;i++){
int oo=v[no][i];
int uu=st[w[no]];
st[w[no]]++;
int u=nu[w[no]];
nu[w[no]]=num;
dfs(oo,no,num);
st[w[no]]=uu;
nu[w[no]]=u;
}
}
else{
ans[no]=ans[la]+num-nu[w[no]];
int pp=v[no].size();
for(int i=0;i<pp;i++){
int oo=v[no][i];
int uu=st[w[no]];
st[w[no]]++;
int u=nu[w[no]];
nu[w[no]]=num;
dfs(oo,no,num);
st[w[no]]=uu;
nu[w[no]]=u;
}
}
}
else{
ans[no]=ans[la]+num;
int pp=v[no].size();
for(int i=0;i<pp;i++){
int oo=v[no][i];
int uu=st[w[no]];
st[w[no]]++;
int u=nu[w[no]];
nu[w[no]]=num+1;
dfs(oo,no,num+1);
st[w[no]]=uu;
nu[w[no]]=u;
}
}
return ;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie();
cout.tie();
int n;
while(cin>>n){
for(int i=1;i<=n;i++){
// a[i]=0;
ans[i]=0;
st[i]=0;
nu[i]=0;
v[i].clear();
}
for(int i=2;i<=n;i++){
int x;
cin>>x;
v[x].push_back(i);
}
for(int i=1;i<=n;i++) cin>>w[i];
st[w[1]]=1;
nu[w[1]]=1;
int pp=v[1].size();
for(int i=0;i<pp;i++) dfs(v[1][i],1,1);
for(int i=2;i<=n;i++) cout<<ans[i]<<endl;
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 151ms
memory: 23580kb
input:
100 1 2 3 4 5 5 7 7 9 10 11 12 13 13 15 13 12 18 12 11 10 7 7 4 25 26 27 4 2 30 31 32 33 34 34 36 34 33 33 33 32 32 30 2 45 1 47 48 49 50 51 52 53 52 55 56 56 52 59 60 59 59 63 64 51 66 49 68 69 68 47 72 73 72 75 76 77 78 79 80 80 82 77 84 77 86 76 88 75 72 91 92 72 94 94 96 97 94 72 55 12 85 53 40 ...
output:
1 3 6 10 15 15 21 21 28 30 38 47 57 57 68 55 47 57 47 38 36 21 21 10 15 21 28 10 3 6 10 15 21 28 28 36 28 21 21 21 15 15 6 3 6 1 3 6 10 15 21 28 36 28 36 45 45 28 36 45 30 36 45 55 21 28 10 15 17 15 3 6 10 6 10 15 21 28 36 45 45 55 21 28 21 28 15 21 10 6 10 15 6 10 10 15 21 10 6 1 3 6 6 10 15 21 28 ...
result:
ok 498996 numbers