제출 #1120084

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1120084		irmuun	Power Plant (JOI20_power)	C++17	47 / 100	1558 ms	80196 KiB

power

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()

const int N=2e5+5;

int n,ans=0;
vector<int>g[N];
string s;
int e[N];
map<pair<int,int>,bool>run;
map<pair<int,int>,int>val;

int dfs(int x,int p){
    if(run[{x,p}]) return val[{x,p}];
    run[{x,p}]=true;
    int cur=0;
    for(int y:g[x]){
        if(y!=p){
            cur+=dfs(y,x);
        }
    }
    cur=max(cur-e[x],e[x]);
    return val[{x,p}]=cur;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin>>n;
    for(int i=1;i<n;i++){
        int a,b;
        cin>>a>>b;
        a--,b--;
        g[a].pb(b);
        g[b].pb(a);
    }
    cin>>s;
    for(int i=0;i<n;i++){
        if(s[i]=='1'){
            e[i]=1;
        }
        else{
            e[i]=0;
        }
    }
    for(int i=0;i<n;i++){
        if(s[i]=='1'){
            dfs(i,i);
            for(int j:g[i]){
                ans=max(ans,val[{j,i}]+1);
            }
            ans=max(ans,val[{i,i}]);
        }
    }
    cout<<ans;
}

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