제출 #210169

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
210169		mohamedsobhi777	친구 (IOI14_friend)	C++14	27 / 100	10 ms	5880 KiB

friend

#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)) ; 
}

• Subtask 1: 0 / 11
• Subtask 2: 8 / 8
• Subtask 3: 0 / 8
• Subtask 4: 19 / 19
• Subtask 5: 0 / 23
• Subtask 6: 0 / 31