Submission #1154137

#	Time	Username	Problem	Language	Result	Execution time	Memory
1154137		brover29	Power Plant (JOI20_power)	C++20	6 / 100	1596 ms	5700 KiB

power

#include <bits/stdc++.h>
//qwerty47924692
using namespace std;
using ll = long long;
const ll N=2e5+29;
const string br="617283";
#define sz(a)(ll)a.size()
#define f first
#define s second
ll tin[N],tout[N],h[N],timer,a[N],ans,dp[N],pr[20][N];
string s;
vector<ll>g[N];
void dfs(ll v){
    tin[v]=++timer;
    for(ll i=1;i<=19;i++)pr[i][v]=pr[i-1][pr[i-1][v]];
    for(ll to:g[v]){
        if(to==pr[0][v])continue;
        pr[0][to]=v;
        dfs(to);
    }
    tout[v]=timer;

}
bool is_parent(ll x,ll y){
    return (tin[x]<=tin[y]&&tout[y]<=tout[x]);
}
ll get(ll x,ll y){
    for(ll i=19;i>=0;i--){
        if(!is_parent(pr[i][x],y))x=pr[i][x];
    }if(!is_parent(x,y))return pr[0][x];
    return x;
}
ll cnt=0,sub=0;
void calc(ll v,ll pr=0){
    if(sub){
        cout<<v<<' '<<dp[v]<<'\n';
    }
    for(ll to:g[v]){
        if(to==pr)continue;
        calc(to,v);
        dp[v]+=dp[to];
    }
    if(s[v]=='1'&&dp[v]){
        cnt++;
        if(a[v])cnt++;
        if(sub)cout<<v<<'\n';
    }
}
//}ll cnt(ll v,ll u){
//    ll lca=get(v,u);
//    return h[u]+h[v]-2*h[lca]+(s[lca]-'0');
//}
ll n;
void f(ll x,ll sum){

    if(x==n){
       // sub=(sum==4&&a[1]&&a[8]&&a[5]&&a[7]);
        for(ll i=1;i<=n;i++)dp[i]=0;
        for(ll i=1;i<=n;i++){
            if(!a[i])continue;
            for(ll j=i+1;j<=n;j++){
                if(!a[j])continue;
//              if(sub)cout<<j<<' '<<pr[i]<<'\n';
//                if(is_parent(j,i)){
//                    swp=1;
//                    swap(i,j);
//                }
                ll x=get(i,j);
//                if(sum==4){
//                    cout<<x<<' '<<i<<' '<<j<<'\n';
//                }
                if(x==i){
                    dp[pr[0][j]]++;
                    dp[x]--;
                    continue;
                }if(x==j){
                    dp[pr[0][i]]++;
                    dp[x]--;
                    continue;
                }
                dp[pr[0][i]]++;
                if(x!=1)dp[pr[0][x]]--;
            //    if(sub)cout<<i<<' '<<pr[0][x]<<'\n';
                dp[pr[0][j]]++;
                dp[x]--;


                  //  if(sub)cout<<j<<' '<<pr[0][x]<<'\n';

//                if(swp)swap(i,j);
            }
        }
        cnt=0;
        calc(1);
//        if(sum-cnt==4){
//            for(ll i=1;i<=n;i++)cout<<a[i]<<' ';
//            cout<<'\n';
//        }
        ans=max(ans,sum-cnt);
        return;
    }
    x++;
    a[x]=0;
    f(x,sum);
    if(s[x]=='1'){
        a[x]=1;
        f(x,sum+1);
    }
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin>>n;
    for(ll i=1;i<n;i++){
        ll v,u;
        cin>>v>>u;
        g[v].push_back(u);
        g[u].push_back(v);
    }
    cin>>s;
    pr[0][1]=1;
    s=' '+s;
    dfs(1);
//    a[1]=1;
//    a[2]=1;
//    a[5]=1;
    f(0,0);
    cout<<ans;

}

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