Submission #763386

#	Time	Username	Problem	Language	Result	Execution time	Memory
763386		vjudge1	Power Plant (JOI20_power)	C++17	100 / 100	124 ms	27936 KiB

power

#include <bits/stdc++.h>

// #pragma GCC optimize("O3,no-stack-protector,fast-math,unroll-loops,tree-vectorize")
// #pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma")

typedef unsigned short u16;
typedef short i16;
typedef unsigned int u32;
typedef int i32;
typedef unsigned long long u64;
typedef long long i64;
typedef float f32;
typedef double f64;
typedef long double f80;
typedef long double f128;

namespace std
{
    template <typename T, typename U>
    struct hash<pair<T, U>>
    {
        size_t operator()(const pair<T, U>& x) const { return hash<T>()(x.first) ^ hash<U>()(x.second); }
    };
}  // namespace std

template <typename T>
using limits = std::numeric_limits<T>;

template <typename T, typename U>
using pa = std::pair<T, U>;

template <typename T, typename U>
using umap = std::unordered_map<T, U>;

#ifdef LOCAL
#include <chrono>

#include "tools.hpp"
#define here(...)                                                                \
    std::cerr << __func__ << ':' << __LINE__ << " [" << #__VA_ARGS__ << "] = ["; \
    _debug(__VA_ARGS__)
#else
#define here(...)
#endif

typedef std::vector<std::vector<u32>> AdjList;

AdjList adj;
std::vector<i32> dp, state;
i32 ans{};

void dfs(u32 u, u32 prev)
{
    i32 sum{}, mx{};
    for (auto& v : adj[u])
    {
        if (v != prev)
        {
            dfs(v, u);
            sum += dp[v];
            mx = std::max(mx, dp[v]);
        }
    }
    if (state[u])
    {
        ans = std::max(ans, std::max(sum - 1, mx + 1));
    }
    else
    {
        ans = std::max(ans, sum);
    }
    dp[u] = std::max(state[u], sum - state[u]);
}

void solve()
{
    u32 n;
    std::cin >> n;
    adj.assign(n, std::vector<u32>());
    dp.assign(n, 0);
    state.assign(n, 0);
    for (u32 i = 0; i < n - 1; ++i)
    {
        u32 u, v;
        std::cin >> u >> v;
        u--, v--;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    for (auto& i : state)
    {
        char ci;
        std::cin >> ci;
        i = ci - '0';
    }
    dfs(0, limits<u32>::max());
    std::cout << ans << '\n';
}

int main()
{
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
#ifdef LOCAL
    using std::chrono::duration_cast;
    using std::chrono::high_resolution_clock;
    using std::chrono::microseconds;
    auto st = high_resolution_clock::now();
    std::ifstream input("./in.txt");
    std::ofstream output("./log/bsol.txt");
    auto cin_buf = std::cin.rdbuf(input.rdbuf());
    auto cout_buf = std::cout.rdbuf(output.rdbuf());
#endif
    solve();
#ifdef LOCAL
    std::cin.rdbuf(cin_buf);
    std::cout.rdbuf(cout_buf);
    input.close();
    output.close();
    auto ed = high_resolution_clock::now();
    std::cerr << "Time elapsed: " << duration_cast<microseconds>(ed - st).count() << " microseconds\n";
#endif
    return 0;
}

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