oj.uz

답안 #210166

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
210166 2020-03-16T17:41:31 Z mohamedsobhi777 친구 (IOI14_friend) C++14
19 / 100
 9 ms 5884 KB 
#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(hst) ; 
            adj[hst].push_back(i) ; 
            confid[i]+=confidence[i] ; 
        }
        else if(prt==1){
            confid[hstn]+=confid[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)) ; 
}

Subtask #1
0 / 11.0

# 결과 실행 시간 메모리 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 5756 KB Output is correct
5 Correct 8 ms 5756 KB Output is correct
6 Correct 8 ms 5752 KB Output is correct
7 Correct 8 ms 5752 KB Output is correct
8 Incorrect 8 ms 5752 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 8 ms 5752 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 8 ms 5880 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 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 5880 KB Output is correct
8 Correct 8 ms 5880 KB Output is correct
9 Correct 8 ms 5880 KB Output is correct
10 Correct 8 ms 5880 KB Output is correct
11 Correct 8 ms 5884 KB Output is correct
12 Correct 8 ms 5884 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

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 8 ms 5880 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 5880 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 9 ms 5752 KB Output is correct
6 Correct 8 ms 5752 KB Output is correct
7 Incorrect 8 ms 5752 KB Output isn't correct
8 Halted 0 ms 0 KB -