10183 | 2024. 03. 29 10:46:32 | 111 | Különböző katicák | cpp17 | Elfogadva 100/100 | 65ms | 46060 KiB |
#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N;
cin>>N;
vector<vector<int>>g(N+1);
vector<int>p(N+1);
for(int i=1;i<=N;i++){
cin>>p[i];
if(i==1){
continue;
}
g[p[i]].push_back(i);
g[i].push_back(p[i]);
}
vector<int>v(N+1);
for(int i=1;i<=N;i++){
cin>>v[i];
}
auto vv=v;
vector<pair<int,int>>w(N+1);
auto dfs=[&](auto self,int i)->pair<int,int>{
pair<int,int>a={v[i],v[i]};
for(int j:g[i]){
pair<int,int>b=j==p[i]?v[j]==-1?pair<int,int>{-1,-1}:pair<int,int>{abs(v[j]-1),v[j]+1}:self(self,j);
if(b.first==-1&&b.second==-1){
continue;
}
if(a.first==-1&&a.second==-1){
a=b;
continue;
}
if(a.first%2!=b.first%2||b.first>a.second||b.second<a.first){
cout<<"NEM"<<'\n';
exit(0);
}
a.first=max(a.first,b.first);
a.second=min(a.second,b.second);
}
w[i]=a;
if(a.first!=-1&&a.second!=-1){
a.first=a.first==0?a.first+1:a.first-1;
a.second++;
}
return a;
};
dfs(dfs,1);
v[1]=w[1].first==-1?1:w[1].first;
auto dfs2=[&](auto self,int i)->void{
for(int j:g[i]){
if(j==p[i]){
continue;
}
if(w[j].first==-1){
v[j]=v[i]+1;
}
else{
if(w[j].first<=v[i]+1&&v[i]+1<=w[j].second){
v[j]=v[i]+1;
}
else{
v[j]=v[i]-1;
}
}
self(self,j);
}
};
dfs2(dfs2,1);
for(int i=1;i<=N;i++){
if(v[i]<0)exit(1);
if(v[i]!=vv[i]&&vv[i]!=-1)exit(1);
for(int j:g[i])if(abs(v[i]-v[j])!=1){
cout<<i<<" "<<v[i]<<endl;
cout<<j<<" "<<v[j]<<endl;
exit(1);
}
}
cout<<"IGEN"<<'\n';
for(int i=1;i<=N;i++){
cout<<v[i]<<' ';
}
cout<<'\n';
return 0;
}
Részfeladat | Összpont | Teszt | Verdikt | Idő | Memória | ||
---|---|---|---|---|---|---|---|
subtask1 | 0/0 | ||||||
1 | Elfogadva | 3ms | 1848 KiB | ||||
2 | Elfogadva | 3ms | 1984 KiB | ||||
3 | Elfogadva | 48ms | 19576 KiB | ||||
subtask2 | 10/10 | ||||||
4 | Elfogadva | 41ms | 17656 KiB | ||||
5 | Elfogadva | 46ms | 19456 KiB | ||||
6 | Elfogadva | 48ms | 20952 KiB | ||||
7 | Elfogadva | 52ms | 22724 KiB | ||||
subtask3 | 15/15 | ||||||
8 | Elfogadva | 46ms | 44860 KiB | ||||
9 | Elfogadva | 43ms | 44684 KiB | ||||
10 | Elfogadva | 65ms | 46060 KiB | ||||
11 | Elfogadva | 57ms | 45032 KiB | ||||
12 | Elfogadva | 54ms | 44100 KiB | ||||
13 | Elfogadva | 56ms | 45028 KiB | ||||
14 | Elfogadva | 54ms | 43644 KiB | ||||
subtask4 | 35/35 | ||||||
15 | Elfogadva | 3ms | 3956 KiB | ||||
16 | Elfogadva | 3ms | 4080 KiB | ||||
17 | Elfogadva | 3ms | 4088 KiB | ||||
18 | Elfogadva | 3ms | 4340 KiB | ||||
19 | Elfogadva | 3ms | 4276 KiB | ||||
20 | Elfogadva | 3ms | 4412 KiB | ||||
21 | Elfogadva | 3ms | 4232 KiB | ||||
22 | Elfogadva | 3ms | 4372 KiB | ||||
subtask5 | 40/40 | ||||||
23 | Elfogadva | 50ms | 22760 KiB | ||||
24 | Elfogadva | 37ms | 23572 KiB | ||||
25 | Elfogadva | 37ms | 24172 KiB | ||||
26 | Elfogadva | 50ms | 22644 KiB | ||||
27 | Elfogadva | 50ms | 22572 KiB | ||||
28 | Elfogadva | 57ms | 23588 KiB | ||||
29 | Elfogadva | 52ms | 23932 KiB | ||||
30 | Elfogadva | 50ms | 23396 KiB | ||||
31 | Elfogadva | 50ms | 23004 KiB | ||||
32 | Elfogadva | 54ms | 23340 KiB | ||||
33 | Elfogadva | 57ms | 24560 KiB |