Submission #1276080

#	Time	Username	Problem	Language	Result	Execution time	Memory
1276080		lamlamlam	Power Plant (JOI20_power)	C++20	100 / 100	74 ms	29072 KiB

power

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define endl '\n'
#define task "JOI20_power"
const int MN = 2e5+5;
struct Dsu{
    int pa[MN],sz[MN];
    Dsu(){
        for(int i=0; i<MN; i++) sz[i] = 1, pa[i] = i;
    }
    int papa(int x){
        if(x==pa[x]) return x;
        return pa[x] = papa(pa[x]);
    }
    void uni_set(int x,int y){
        x = papa(x);
        y = papa(y);
        if(x==y) return;
        if(x>y) swap(x,y);
        sz[x] += sz[y];
        pa[y] = x;
    }
} dsu;
int n,u,v,ans,f[MN],g[MN];
bool has_power[MN];
vector<int> adj[MN];
vector<pii> edges;
void dfs(int u,int p){
    for(auto v:adj[u]) if(v!=p){
        dfs(v,u);
        if(has_power[v]) f[u] += max(1,f[v]);
        else f[u] += f[v];
    }
    if(has_power[u] and f[u]) f[u]--;
    if(has_power[p]) ans = max(ans,f[u]+1), g[u] = f[u]+1;
    else ans = max(ans,f[u]), g[u] = f[u];
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    if(fopen(task".inp","r")){
        freopen(task".inp","r",stdin);
        freopen(task".out","w",stdout);
    }
    cin >> n;
    for(int i=1; i<n; i++){
        cin >> u >> v;
        edges.push_back({u,v});
    }
    string s; cin >> s;
    if(n==1) {
        cout << (s[0]=='1');
        return 0;
    }
    for(int i=1; i<=n; i++) has_power[i] = (s[i-1]=='1');
    for(auto e:edges){
        u = e.first, v = e.second;
        if(!has_power[u] and !has_power[v]) dsu.uni_set(u,v);
    }
    for(auto e:edges){
        u = e.first, v = e.second;
        if(!has_power[u] and !has_power[v]) continue;
        u = dsu.papa(u); v = dsu.papa(v);
        if(has_power[u] and has_power[v]) ans = 2;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs(1,0);
//    for(int i=1; i<=n; i++) cerr << f[i] << ' '; cerr << endl;
//    for(int i=1; i<=n; i++) cerr << g[i] << ' '; cerr << endl;
    cout << ans;
    cerr << "\nThoi gian loj: " << clock() << endl;
}

Compilation message (stderr)

power.cpp: In function 'int main()':
power.cpp:46:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |         freopen(task".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
power.cpp:47:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |         freopen(task".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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