Submission #1276079

#	Time	Username	Problem	Language	Result	Execution time	Memory
1276079		lamlamlam	Power Plant (JOI20_power)	C++20	6 / 100	124 ms	584 KiB

power

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define pb push_back
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define endl '\n'
#define task "2"
const int MN =  2e5+5;
int n,u,v,has_power[MN],pa[MN],h[MN],ans;
vector<int> adj[MN],generators;
void dfs(int u,int p){
    pa[u] = p;
    h[u] = h[p] + 1;
    for(auto v:adj[u]) if(v!=p) dfs(v,u);
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;
    if(n>20){
        cerr << "N IS TOO BIG: N = " << n << endl;
        return 0;
    }
    for(int i=1; i<n; i++){
        cin >> u >> v;
        adj[u].pb(v);
        adj[v].pb(u);
    }
    string s; cin >> s;
    for(int i=1; i<=n; i++) if(s[i-1]=='1'){
        generators.pb(i);
        has_power[i] = 1;
    }
    dfs(1,0);
    int sz = generators.size();
    for(int mask=0; mask<(1<<sz); mask++){
        bitset<20> activated = 0, broken = 0;
        vector<int> filtered;
        for(int i=0; i<sz; i++) if(1&(mask>>i)) filtered.push_back(generators[i]);
        for(auto u:filtered) activated[u] = 1;
        for(auto u:filtered){
            for(auto v:filtered){
                if(u>=v) continue;
                vector<int> path;
                int x = u, y = v;
                if(h[x]<h[y]) swap(x,y);
                while(h[x]>h[y]){
                    x = pa[x];
                    if(x!=y) path.pb(x);
                }
                while(x!=y){
                    x = pa[x]; y = pa[y];
                    path.pb(x);
                    if(x!=y) path.pb(y);
                }
                for(auto x:path) if(has_power[x]) activated[x] = 0, broken[x] = 1;
//                cerr << "PATH: " << u << ' ' << v << ": ";
//                for(auto x:path) cerr << x << ' '; cerr << endl;
            }
        }
        ans = max(ans,(int)activated.count()-(int)broken.count());
    }
    cout << ans;
    cerr << "\nThoi gian loj: " << clock() << endl;
}

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