#include<bits/stdc++.h>
using namespace std;
int A[200009],H[200009],C[200009];
int a,b,c,d,e,i,j,ii,jj,zx,xc;
long long dp[5003][5003];
//pair <pair <int, int>, int> p[200009];
vector <int> v[200009];
void dfs(int q, int w){
for(j=1; j<=5000; j++){
if(j!=H[q]) dp[q][j]+=C[q];
}
for(vector <int>::iterator it=v[q].begin(); it!=v[q].end(); it++){
if((*it)==w) continue;
dfs((*it),q);
for(j=1; j<=5000; j++){
dp[q][j]+=dp[(*it)][j];
}
}
for(j=4999; j>=1; j--){
dp[q][j]=min(dp[q][j+1],dp[q][j]);
}
}
int main(){
ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
map <int, int> mp;
map <int, int>::iterator it;
cin>>a;
for(i=1; i<=a; i++){
//cin>>p[i].first.first>>p[i].first.second>>p[i].second;
cin>>A[i]>>H[i]>>C[i];
mp[H[i]]++;
}
zx=0;
for(it=mp.begin(); it!=mp.end(); it++){
zx++;
(*it).second=zx;
}
for(i=1; i<=a; i++){
H[i]=mp[H[i]];
}
for(i=2; i<=a; i++){
v[A[i]].push_back(i);
}
dfs(1,0);
cout<<dp[1][1];
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
5068 KB |
Output is correct |
2 |
Correct |
3 ms |
5068 KB |
Output is correct |
3 |
Correct |
3 ms |
5144 KB |
Output is correct |
4 |
Correct |
3 ms |
5068 KB |
Output is correct |
5 |
Correct |
236 ms |
201120 KB |
Output is correct |
6 |
Correct |
227 ms |
200900 KB |
Output is correct |
7 |
Correct |
235 ms |
200928 KB |
Output is correct |
8 |
Correct |
234 ms |
201336 KB |
Output is correct |
9 |
Correct |
233 ms |
201048 KB |
Output is correct |
10 |
Correct |
232 ms |
201040 KB |
Output is correct |
11 |
Correct |
227 ms |
200996 KB |
Output is correct |
12 |
Correct |
233 ms |
201668 KB |
Output is correct |
13 |
Correct |
234 ms |
201584 KB |
Output is correct |
14 |
Correct |
235 ms |
201540 KB |
Output is correct |
15 |
Correct |
233 ms |
201248 KB |
Output is correct |
16 |
Correct |
236 ms |
201292 KB |
Output is correct |
17 |
Correct |
232 ms |
201168 KB |
Output is correct |
18 |
Correct |
227 ms |
201040 KB |
Output is correct |
19 |
Correct |
244 ms |
201536 KB |
Output is correct |
20 |
Correct |
230 ms |
201156 KB |
Output is correct |
21 |
Correct |
230 ms |
201264 KB |
Output is correct |
22 |
Correct |
235 ms |
201268 KB |
Output is correct |
23 |
Correct |
226 ms |
201028 KB |
Output is correct |
24 |
Correct |
229 ms |
201540 KB |
Output is correct |
25 |
Correct |
232 ms |
201356 KB |
Output is correct |
26 |
Correct |
233 ms |
201684 KB |
Output is correct |
27 |
Correct |
231 ms |
201400 KB |
Output is correct |
28 |
Correct |
236 ms |
201672 KB |
Output is correct |
29 |
Correct |
231 ms |
201592 KB |
Output is correct |
30 |
Correct |
232 ms |
201444 KB |
Output is correct |
31 |
Correct |
236 ms |
201644 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
5068 KB |
Output is correct |
2 |
Correct |
3 ms |
5068 KB |
Output is correct |
3 |
Correct |
3 ms |
5144 KB |
Output is correct |
4 |
Correct |
3 ms |
5068 KB |
Output is correct |
5 |
Correct |
236 ms |
201120 KB |
Output is correct |
6 |
Correct |
227 ms |
200900 KB |
Output is correct |
7 |
Correct |
235 ms |
200928 KB |
Output is correct |
8 |
Correct |
234 ms |
201336 KB |
Output is correct |
9 |
Correct |
233 ms |
201048 KB |
Output is correct |
10 |
Correct |
232 ms |
201040 KB |
Output is correct |
11 |
Correct |
227 ms |
200996 KB |
Output is correct |
12 |
Correct |
233 ms |
201668 KB |
Output is correct |
13 |
Correct |
234 ms |
201584 KB |
Output is correct |
14 |
Correct |
235 ms |
201540 KB |
Output is correct |
15 |
Correct |
233 ms |
201248 KB |
Output is correct |
16 |
Correct |
236 ms |
201292 KB |
Output is correct |
17 |
Correct |
232 ms |
201168 KB |
Output is correct |
18 |
Correct |
227 ms |
201040 KB |
Output is correct |
19 |
Correct |
244 ms |
201536 KB |
Output is correct |
20 |
Correct |
230 ms |
201156 KB |
Output is correct |
21 |
Correct |
230 ms |
201264 KB |
Output is correct |
22 |
Correct |
235 ms |
201268 KB |
Output is correct |
23 |
Correct |
226 ms |
201028 KB |
Output is correct |
24 |
Correct |
229 ms |
201540 KB |
Output is correct |
25 |
Correct |
232 ms |
201356 KB |
Output is correct |
26 |
Correct |
233 ms |
201684 KB |
Output is correct |
27 |
Correct |
231 ms |
201400 KB |
Output is correct |
28 |
Correct |
236 ms |
201672 KB |
Output is correct |
29 |
Correct |
231 ms |
201592 KB |
Output is correct |
30 |
Correct |
232 ms |
201444 KB |
Output is correct |
31 |
Correct |
236 ms |
201644 KB |
Output is correct |
32 |
Incorrect |
231 ms |
201264 KB |
Output isn't correct |
33 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
5068 KB |
Output is correct |
2 |
Correct |
3 ms |
5068 KB |
Output is correct |
3 |
Correct |
3 ms |
5144 KB |
Output is correct |
4 |
Correct |
3 ms |
5068 KB |
Output is correct |
5 |
Correct |
236 ms |
201120 KB |
Output is correct |
6 |
Correct |
227 ms |
200900 KB |
Output is correct |
7 |
Correct |
235 ms |
200928 KB |
Output is correct |
8 |
Correct |
234 ms |
201336 KB |
Output is correct |
9 |
Correct |
233 ms |
201048 KB |
Output is correct |
10 |
Correct |
232 ms |
201040 KB |
Output is correct |
11 |
Correct |
227 ms |
200996 KB |
Output is correct |
12 |
Correct |
233 ms |
201668 KB |
Output is correct |
13 |
Correct |
234 ms |
201584 KB |
Output is correct |
14 |
Correct |
235 ms |
201540 KB |
Output is correct |
15 |
Correct |
233 ms |
201248 KB |
Output is correct |
16 |
Correct |
236 ms |
201292 KB |
Output is correct |
17 |
Correct |
232 ms |
201168 KB |
Output is correct |
18 |
Correct |
227 ms |
201040 KB |
Output is correct |
19 |
Correct |
244 ms |
201536 KB |
Output is correct |
20 |
Correct |
230 ms |
201156 KB |
Output is correct |
21 |
Correct |
230 ms |
201264 KB |
Output is correct |
22 |
Correct |
235 ms |
201268 KB |
Output is correct |
23 |
Correct |
226 ms |
201028 KB |
Output is correct |
24 |
Correct |
229 ms |
201540 KB |
Output is correct |
25 |
Correct |
232 ms |
201356 KB |
Output is correct |
26 |
Correct |
233 ms |
201684 KB |
Output is correct |
27 |
Correct |
231 ms |
201400 KB |
Output is correct |
28 |
Correct |
236 ms |
201672 KB |
Output is correct |
29 |
Correct |
231 ms |
201592 KB |
Output is correct |
30 |
Correct |
232 ms |
201444 KB |
Output is correct |
31 |
Correct |
236 ms |
201644 KB |
Output is correct |
32 |
Incorrect |
231 ms |
201264 KB |
Output isn't correct |
33 |
Halted |
0 ms |
0 KB |
- |