Submission #309883

#	Time	Username	Problem	Language	Result	Execution time	Memory
309883		adrianbudau	Power Plant (JOI20_power)	C++17	100 / 100	188 ms	31744 KiB

power

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class Tree {
  public:
    Tree(int size): m_edges(size), m_generators(size, 0) {}

    void add_edge(int from, int to) {
        m_edges[from].emplace_back(to);
        m_edges[to].emplace_back(from);
    }

    void set_generator(int node) {
        m_generators[node]++;
    }

    int best() const {
        return dfs(0).first;
    }

  private:
    pair<int, int> dfs(int node, int father = -1) const {
        int bestdown = m_generators[node];
        int bestfull = m_generators[node];

        int sum = 0;
        for (auto &x : m_edges[node]) {
            if (x == father)
                continue;
            auto [a, b] = dfs(x, node);
            bestdown = max({bestdown, a, b + m_generators[node]});
            sum += b;
        }
        bestfull = max(bestfull, sum - m_generators[node]);
        bestdown = max(bestdown, bestfull);
        return {bestdown, bestfull};
    }

    vector< vector<int> > m_edges;
    vector<int> m_generators;
};

int main() {
    ios::sync_with_stdio(false);

    int N; cin >> N;
    Tree T(N);
    for (int i = 1; i < N; ++i) {
        int x, y; cin >> x >> y;
        T.add_edge(x - 1, y - 1);
    }

    string S; cin >> S;
    for (int i = 0; i < N; ++i)
        if (S[i] == '1')
            T.set_generator(i);

    cout << T.best() << "\n";
}

• Subtask 1: 6 / 6
• Subtask 2: 41 / 41
• Subtask 3: 53 / 53