Submission #827433

#	Time	Username	Problem	Language	Result	Execution time	Memory
827433		tset	Power Plant (JOI20_power)	C++14	100 / 100	155 ms	42188 KiB

power

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

vector<vector<int > > nxt;
vector<int > pereDe; 
vector<vector<int > > filsDe;
vector<int > dp;
string isPower;
int ansFinale = 0;


void dfsInit(int nde, int prc)
{
    pereDe[nde] = prc;
    for(int iV : nxt[nde])
    {
        if(iV != prc)
        {
            filsDe[nde].push_back(iV);
            dfsInit(iV, nde);
        }
    }
}

int fDp(int nde)
{
    bool isNdePower = isPower[nde] == '1'? true : false;
    if(dp[nde] != -1)
    {
        return dp[nde];
    }
    int ans = 0;
    int ansSortant = 0;
    for(int iF : filsDe[nde])
    {
        int resFils = fDp(iF);
        if(isNdePower)
        {
            ansFinale = max(ansFinale, resFils +1);// On s'arrete ici.
        }
        ansSortant += resFils;
    }
    if(isNdePower)
    {
        ans = max(ans, ansSortant-1);
        ans = max(ans, 1ll);
    }
    else
    {
        ans = max(ans, ansSortant);
    }
    dp[nde] = ans;
    return ans;
}

signed main()
{
    int N;
    scanf("%lld", &N);
    int nbArcs = N-1;
    nxt.resize(N);
    pereDe.resize(N); 
    filsDe.resize(N);
    dp.assign(N, -1);
    for(int iArc = 0; iArc < nbArcs; iArc++)
    {
        int u, v;
        scanf("%lld%lld\n", &u, &v);
        --u; --v;
        nxt[u].push_back(v);
        nxt[v].push_back(u);
    }

    int root = 0;
    dfsInit(root, root);

    cin >> isPower;
    int ans = fDp(root);
    printf("%lld\n", max(ans, ansFinale));
}

Compilation message (stderr)

power.cpp: In function 'int main()':
power.cpp:60:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |     scanf("%lld", &N);
      |     ~~~~~^~~~~~~~~~~~
power.cpp:69:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |         scanf("%lld%lld\n", &u, &v);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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