Submission #992587

#	Time	Username	Problem	Language	Result	Execution time	Memory
992587		vysniak_grossmeister	Power Plant (JOI20_power)	C++17	0 / 100	2 ms	7516 KiB

power

#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,tune=native")
using namespace std;

const int N = 1e5 * 2ll;

typedef long long ll;

vector<ll>g[N];

ll h[N], sz[N], pr[N];
ll mx = 0ll;

void push(ll v){

    sz[v]++;

    while(v != -1ll){

        v = pr[v];

        sz[v]++;

    }

}

ll get(ll v){
ll ans = -1ll;

while(v != -1ll){

    v = pr[v];

    ans = max(ans, sz[v]);


}

return ans;

}

map<ll, set<ll> >mp;

void calc_dfs(ll v, ll p, ll H){

mp[H].insert(v);



h[v] = H;

pr[v] = p;

mx = max(mx, H);

for(auto x : g[v]){

    if(x != p){

        calc_dfs(x, v, H + 1ll);

    }

}

}



int main(){
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);

ll n;
cin >> n;

for(ll i = 1; i <= n - 1; ++i){
    ll a, b;
    cin >> a >> b;
    g[a].push_back(b);
    g[b].push_back(a);
}

string s;
cin >> s;

calc_dfs(1ll, -1ll, 0ll);
ll ans = 0ll;
for(ll k = mx; k >= 0; --k){
    ///cout << mx << ' ' << k << endl;
    for(auto v : mp[k]){
        //cout << k << ' ' << v << endl;
        if(s[v - 1] == '1'){

            ///cout << '!' << ' ' << v << endl;

            if(sz[v] == 0){

                push(v);
                ans += 1;

            }
            else if(sz[v] == 1){

                ll g = get(v);

               /// cout << '?' << ' ' << v << ' ' << g << endl;

                if(g <= 1ll){

                    push(v);

                    ans += 1;

                }

            }

        }

    }

}

cout << ans << endl;

return 0;

}

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