QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#382498#3748. 买一送一秦始皇派蒙恬还原神舟十二 (Jiancong Wen, Chu Jin, Zekai Zhang)AC ✓151ms23580kbC++171.7kb2024-04-08 15:33:372024-04-08 15:33:37

Judging History

This is the latest submission verdict.

  • [2024-04-08 15:33:37]
  • Judged
  • Verdict: AC
  • Time: 151ms
  • Memory: 23580kb
  • [2024-04-08 15:33:37]
  • Submitted

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