제출 #385984

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
385984		Keshi	친구 (IOI14_friend)	C++17	100 / 100	57 ms	11648 KiB

friend

    //In the name of God
    #include <bits/stdc++.h>
    #include "friend.h"
    using namespace std;
     
    typedef long long ll;
    typedef pair<ll, ll> pll;
     
    const ll maxn = 2e5 + 100;
    const ll mod = 1e9 + 7;
    const ll inf = 1e18;
     
    #define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    #define file_io freopen("input.txt", "r+", stdin);freopen("output.txt", "w+", stdout);
    #define pb push_back
    #define Mp make_pair
    #define F first
    #define S second
    #define Sz(x) ll((x).size())
    #define all(x) (x).begin(), (x).end()
     
    ll c[maxn], pr[maxn], dp[maxn][2];
    vector<ll> g[maxn];
     
    void dfs(ll v){
    	reverse(all(g[v]));
    	dp[v][1] = c[v];
    	for(ll u : g[v]){
    		dfs(u);
    		if(pr[u] == 0){
    			dp[v][1] += dp[u][0];
    			dp[v][0] += max(dp[u][0], dp[u][1]);
    		}
    		if(pr[u] == 1){
    			dp[v][1] = max(dp[v][0], dp[v][1]) + max(dp[u][0], dp[u][1]);
    			dp[v][0] += dp[u][0];
    		}
    		if(pr[u] == 2){
    			dp[v][1] = max(dp[v][1] + dp[u][0], dp[v][0] + dp[u][1]);
    			dp[v][0] += dp[u][0];
    		}
    	}
    	return;
    }
     
    int findSample(int n,int confidence[],int host[],int protocol[]){
    	for(ll i = 0; i < n; i++){
    		c[i] = confidence[i];
    	}
    	for(ll i = 1; i < n; i++){
    		pr[i] = protocol[i];
    		g[host[i]].pb(i);
    	}
    	dfs(0);
    	return max(dp[0][0], dp[0][1]);
    }
     
    /*int main(){
        fast_io;
     
     
     
        return 0;
    }
    */

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