#include<bits/stdc++.h>
#include<friend.h>
using namespace std ;
const int N = 1e5 + 5 ;
vector<int> adj[N] ;
vector<int> rep[N] ;
int confid[N] ;
struct DSU{
vector<int> fat ;
void init(int n){
fat.resize(n +1) ;
for(int i =0 ; i < n; i++){
fat[i] = i ;
}
}
int fin(int x)
{
return fat[x] = (fat[x]==x?x:fin(fat[x])) ;
}
void unio(int a , int b){
int aa = fin(a) ;
int bb = fin(b) ;
if(aa!=bb){
fat[aa] = bb ;
}
}
};
int dp[N][2] ;
int solve(int x, int p , int l){
if(dp[x][l]!=-1)
return dp[x][l] ;
int ret = 0 ;
if(l){
ret+=confid[x] ;
}
for(auto u : adj[x]) {
if(p==u)continue ;
if(!l){
ret+=max(solve(u , x , 1) , solve(u , x , 0) );
}
else {
ret+=solve(u ,x , 0) ;
}
}
return dp[x][l] = ret;
}
int findSample(int n , int confidence[] , int host[] , int protocol[]){
memset(dp , -1 , sizeof dp) ;
DSU d1 ;
d1.init(n+1) ;
confid[0] = confidence[0] ;
for(int i = 1 ; i < n; i++){
int hst = host[i] ;
int hstn = d1.fin(hst) ;
int prt = protocol[i] ;
if(!prt){
adj[i].push_back(hstn) ;
adj[hstn].push_back(i) ;
confid[i]+=confidence[i] ;
}
else if(prt==1){
confid[hstn]+=confidence[i] ;
d1.unio(i , hstn) ;
}
else {
confid[i]+=confidence[i] ;
rep[hstn].push_back(i) ;
}
}
for(int i = 0 ; i <n ; i++){
for(auto u : rep[i]){
confid[i] = max(confid[i] , confid[u]) ;
}
}
return max(solve(0 , 0 , 0) , solve(0 , 0 , 1)) ;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
8 ms |
5752 KB |
Output is correct |
2 |
Correct |
8 ms |
5752 KB |
Output is correct |
3 |
Correct |
8 ms |
5752 KB |
Output is correct |
4 |
Correct |
7 ms |
5752 KB |
Output is correct |
5 |
Correct |
8 ms |
5752 KB |
Output is correct |
6 |
Correct |
8 ms |
5752 KB |
Output is correct |
7 |
Correct |
8 ms |
5756 KB |
Output is correct |
8 |
Incorrect |
8 ms |
5752 KB |
Output isn't correct |
9 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
8 ms |
5752 KB |
Output is correct |
2 |
Correct |
8 ms |
5752 KB |
Output is correct |
3 |
Correct |
8 ms |
5748 KB |
Output is correct |
4 |
Correct |
8 ms |
5752 KB |
Output is correct |
5 |
Correct |
8 ms |
5880 KB |
Output is correct |
6 |
Correct |
9 ms |
5752 KB |
Output is correct |
7 |
Correct |
8 ms |
5880 KB |
Output is correct |
8 |
Correct |
8 ms |
5752 KB |
Output is correct |
9 |
Correct |
8 ms |
5752 KB |
Output is correct |
10 |
Correct |
8 ms |
5752 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
8 ms |
5752 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
8 ms |
5752 KB |
Output is correct |
2 |
Correct |
8 ms |
5752 KB |
Output is correct |
3 |
Correct |
8 ms |
5880 KB |
Output is correct |
4 |
Correct |
8 ms |
5752 KB |
Output is correct |
5 |
Correct |
8 ms |
5880 KB |
Output is correct |
6 |
Correct |
8 ms |
5880 KB |
Output is correct |
7 |
Correct |
8 ms |
5756 KB |
Output is correct |
8 |
Correct |
8 ms |
5880 KB |
Output is correct |
9 |
Correct |
8 ms |
5752 KB |
Output is correct |
10 |
Correct |
10 ms |
5880 KB |
Output is correct |
11 |
Correct |
8 ms |
5752 KB |
Output is correct |
12 |
Correct |
9 ms |
5880 KB |
Output is correct |
13 |
Correct |
8 ms |
5880 KB |
Output is correct |
14 |
Correct |
8 ms |
5752 KB |
Output is correct |
15 |
Correct |
8 ms |
5880 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
8 ms |
5752 KB |
Output is correct |
2 |
Correct |
8 ms |
5752 KB |
Output is correct |
3 |
Correct |
8 ms |
5876 KB |
Output is correct |
4 |
Correct |
8 ms |
5880 KB |
Output is correct |
5 |
Correct |
8 ms |
5752 KB |
Output is correct |
6 |
Correct |
8 ms |
5752 KB |
Output is correct |
7 |
Correct |
8 ms |
5752 KB |
Output is correct |
8 |
Correct |
8 ms |
5880 KB |
Output is correct |
9 |
Correct |
9 ms |
5880 KB |
Output is correct |
10 |
Correct |
8 ms |
5880 KB |
Output is correct |
11 |
Incorrect |
8 ms |
5880 KB |
Output isn't correct |
12 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
8 ms |
5752 KB |
Output is correct |
2 |
Correct |
8 ms |
5752 KB |
Output is correct |
3 |
Correct |
8 ms |
5752 KB |
Output is correct |
4 |
Correct |
8 ms |
5880 KB |
Output is correct |
5 |
Correct |
8 ms |
5752 KB |
Output is correct |
6 |
Correct |
7 ms |
5752 KB |
Output is correct |
7 |
Incorrect |
8 ms |
5752 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |