Submission #936343

#	Time	Username	Problem	Language	Result	Execution time	Memory
936343		ace5	Power Plant (JOI20_power)	C++17	100 / 100	168 ms	42420 KiB

power

#include <bits/stdc++.h>

using namespace std;

#define int int64_t

vector<vector<int>> g;
vector<int> dpn;
vector<int> dpy;
vector<bool> gen;

void dfs(int v,int p)
{
    vector<int> sdpy,sdpn;
    for(auto u:g[v])
    {
        if(u != p)
        {
            dfs(u,v);
            sdpy.push_back(dpy[u]);
            sdpn.push_back(dpn[u]);
        }
    }
    if(gen[v] == 0)
    {
        for(int i = 0;i < sdpy.size();++i)
        {
            dpy[v] += sdpy[i];
        }
        dpn[v] = dpy[v];
        int v2 = 0;
        for(int i = 0;i < sdpn.size();++i)
        {
            v2 = max(v2,sdpn[i]);
        }
        dpn[v] = max(dpn[v],v2);
    }
    else
    {
        for(int i = 0;i < sdpy.size();++i)
        {
            dpy[v] += sdpy[i];
        }
        dpy[v] --;
        dpy[v] = max(dpy[v],int64_t(1));
        for(int i = 0;i < sdpy.size();++i)
        {
            dpn[v] += sdpy[i];
        }
        dpn[v]--;
        int v2 = 0;
        for(int i =0;i < sdpy.size();++i)
        {
            v2 = max(v2,sdpy[i]);
        }
        v2++;
        dpn[v] = max(dpn[v],v2);
        int v3 = 0;
        for(int i = 0;i < sdpn.size();++i)
        {
            v3 = max(v3,sdpn[i]);
        }
        dpn[v] = max(dpn[v],v3);
    }
    //cout << v << ' ' << dpy[v] << ' ' << dpn[v] << "\n";
    return ;
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    g.resize(n);
    dpn.resize(n);
    dpy.resize(n);
    gen.resize(n);
    for(int i = 0;i < n-1;++i)
    {
        int u,v;
        cin >> u >> v;
        u--;
        v--;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    string s;
    cin >> s;
    for(int i =0 ;i < n;++i)
    {
        gen[i] = (s[i] == '1');
    }
    dfs(0,-1);
    cout << dpn[0] << "\n";
}

Compilation message (stderr)

power.cpp: In function 'void dfs(int64_t, int64_t)':
power.cpp:26:25: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |         for(int i = 0;i < sdpy.size();++i)
      |                       ~~^~~~~~~~~~~~~
power.cpp:32:25: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |         for(int i = 0;i < sdpn.size();++i)
      |                       ~~^~~~~~~~~~~~~
power.cpp:40:25: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |         for(int i = 0;i < sdpy.size();++i)
      |                       ~~^~~~~~~~~~~~~
power.cpp:46:25: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |         for(int i = 0;i < sdpy.size();++i)
      |                       ~~^~~~~~~~~~~~~
power.cpp:52:24: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |         for(int i =0;i < sdpy.size();++i)
      |                      ~~^~~~~~~~~~~~~
power.cpp:59:25: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |         for(int i = 0;i < sdpn.size();++i)
      |                       ~~^~~~~~~~~~~~~

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