Official

C - 組織のアンバランス / Imbalance of the Organization Editorial by MMNMM Editorial for printing


この問題は、社員番号の大きいほうから順に

  • その社員のチーム仕事量
  • その社員のアンバランス度

を求めていくことで答えを計算することができます。

それぞれの社員に対して、直属の部下の一覧を作っておくことでシンプルに処理を行うことができます。

実装例は以下のようになります。

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int N;
    cin >> N;
    vector<vector<int>> children(N); // 社員 i の直属の部下の一覧
    for (int i = 1; i < N; ++i) {
        int p;
        cin >> p;
        children[p - 1].emplace_back(i); // 上司のリストに自分を入れる
    }

    vector<int> single_work(N); // 社員 i の仕事量
    vector<long> team_work(N); // 社員 i のチーム仕事量
    for (int& w : single_work) {
        cin >> w;
    }

    long unbalanceness = 0;
    for (int i = N; i--; ) {
        team_work[i] = single_work[i];
        if (!empty(children[i])) { // 部下がいれば
            long min_team_work = 200000000000000, max_team_work = 0; // 部下のチーム仕事量の最小と最大を求める
            for (const int child : children[i]) {
                team_work[i] += team_work[child];
                min_team_work = min(min_team_work, team_work[child]);
                max_team_work = max(max_team_work, team_work[child]);
            }
            unbalanceness = max(unbalanceness, max_team_work - min_team_work); // 組織のアンバランス度は個人のアンバランス度の最大値
        }
    }

    // 答えを出力
    cout << unbalanceness << endl;
    return 0;
}
N = int(input())

children = [[] for _ in range(N)]
for i, p in enumerate(map(int, input().split())):
    children[p - 1].append(i + 1) # 上司のリストに自分を入れる

single_work = list(map(int, input().split())) # 社員 i の仕事量
team_work = [0 for _ in range(N)] # 社員 i のチーム仕事量

unbalanceness = 0
for i in reversed(range(N)):
    team_work[i] = single_work[i]
    if len(children[i]) > 0: # 部下がいれば
        min_team_work = 200000000000000
        max_team_work = 0 # 部下のチーム仕事量の最小と最大を求める
        for child in children[i]:
            team_work[i] += team_work[child]
            min_team_work = min(min_team_work, team_work[child])
            max_team_work = max(max_team_work, team_work[child])
        unbalanceness = max(unbalanceness, max_team_work - min_team_work) # 組織のアンバランス度は個人のアンバランス度の最大値

# 答えを出力
print(unbalanceness)

posted:
last update: