Submission #850764

#	Time	Username	Problem	Language	Result	Execution time	Memory
850764		oscar1f	Power Plant (JOI20_power)	C++17	100 / 100	105 ms	27028 KiB

power

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

const int MAX_SOM=200*1000+5;
int nbSom,debAre,finAre,rep;
vector<int> adja[MAX_SOM];
int val[MAX_SOM],dv[MAX_SOM];
string etatDeb;

int DFS(int pos) {
    if (dv[pos]==0) {
        dv[pos]=1;
        int somme=0,maxi=0,ans;
        for (int i:adja[pos]) {
            ans=DFS(i);
            somme+=ans;
            maxi=max(maxi,ans);
        }
        //cout<<pos<<" "<<maxi<<" "<<somme<<endl;
        rep=max(rep,max(maxi+val[pos],somme-val[pos]));
        return max(somme-val[pos],val[pos]);
    }
    else {
        return 0;
    }
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>nbSom;
    for (int i=0;i<nbSom-1;i++) {
        cin>>debAre>>finAre;
        adja[debAre].push_back(finAre);
        adja[finAre].push_back(debAre);
    }
    cin>>etatDeb;
    for (int i=1;i<=nbSom;i++) {
        if (etatDeb[i-1]=='1') {
            val[i]=1;
        }
    }
    DFS(1);
    cout<<rep<<endl;
    return 0;
}

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