제출 #1108650

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1108650		Ariadna	친구 (IOI14_friend)	C++14	19 / 100	1 ms	592 KiB

friend

#include <bits/stdc++.h>
using namespace std;

vector<int> dp0, dp1;

int dfs1(int u, int p, vector<vector<int>>& adj, vector<int>& conf);
int dfs0(int u, int p, vector<vector<int>>& adj, vector<int>& conf) {
    if (dp0[u] != -1) return dp0[u];
    dp0[u] = 0;
    for (int v: adj[u]) {
        if (v == p) continue;
        dp0[u] += max(dfs0(v, u, adj, conf), dfs1(v, u, adj, conf));
    }
    return dp0[u];
}

int dfs1(int u, int p, vector<vector<int>>& adj, vector<int>& conf) {
    if (dp1[u] != -1) return dp1[u];
    dp1[u] = conf[u];
    for (int v: adj[u]) {
        if (v == p) continue;;
        dp1[u] += dfs0(v, u, adj, conf);
    }
    return dp1[u];
}

int findSample(int n, int confidence[], int host[], int protocol[]) {
    vector<vector<int>> adj(n);
    for (int i = 1; i < n; ++i) {
        adj[host[i]].push_back(i);
        adj[i].push_back(host[i]);
    }

    dp0 = dp1 = vector<int>(n, -1);
    vector<int> conf(n);
    for (int i = 0; i < n; ++i) conf[i] = confidence[i];

    return max(dfs0(0, 0, adj, conf), dfs1(0, 0, adj, conf));
}

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