Submission #1118596

#	Time	Username	Problem	Language	Result	Execution time	Memory
1118596		Choco	Paprike (COI18_paprike)	C++17	13 / 100	60 ms	18112 KiB

paprike

#include<bits/stdc++.h>
using namespace std;
#define Study ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define ll long long
#define ull unsigned long long
#define pb push_back
#define ff first 
#define ss second
#define ins insert
#define all(x) x.begin(),x.end()
#define fori(x,y,z) for(ll x=y;x<=z;x++)
const ll INF=1e9;
const ll sz=1e5+10;
const ll mod=1e9+7;
vector<vector<ll>>graph;
vector<ll>check,parent,value,a,cr;
ll k;
void dfs(ll s,ll p=-1){
    check[s]=1;
    parent[s]=p;
    value[s]+=a[s];
    for(auto i:graph[s]){
        if(!check[i]){
        dfs(i,s);
        value[s]+=value[i];
        }
    }
}
bool temp(ll x,ll y){
    return value[x]>=value[y];
}
ll cuts=0;
void dfs1(ll s){
    if(value[s]>k){
        for(auto i:graph[s]){
            if(i==parent[s])
            continue;
            if(value[i]>k){
                dfs1(i);
                cr[s]+=cr[i];
            }
            if(value[i]<=k and value[s]-cr[s]>k){
                //cout<<i<<' '<<s<<endl;
                cr[s]+=value[i];
                parent[i]=-1;
                cuts++;
            }
            if(value[s]-cr[s]<=k)
            break;
        }
        value[s]-=cr[s];
    }
}
void work(){
    ll n;
    cin>>n>>k;
    graph.resize(n+10);
    check.assign(n+10,0);
    parent.assign(n+10,-1);
    value.assign(n+10,0);
    a.resize(n+10);
    cr.assign(n+10,0);
    ll csum=0;
    fori(i,1,n)
    cin>>a[i];
    fori(i,1,n-1){
        ll x,y;
        cin>>x>>y;
        graph[x].pb(y);
        graph[y].pb(x);
    }
    dfs(1);
    //fori(i,1,n)
    //cout<<value[i]<<' ';
    //cout<<endl;
    fori(i,1,n){
        sort(all(graph[i]),temp);
    }
    dfs1(1);
    
    cout<<cuts;
}
int main(){
    Study;
    ll t=1;
    //cin>>t;
    while(t--){
        work();
    }
}

Compilation message (stderr)

paprike.cpp: In function 'void work()':
paprike.cpp:63:8: warning: unused variable 'csum' [-Wunused-variable]
   63 |     ll csum=0;
      |        ^~~~

• Subtask 1: 0 / 11
• Subtask 2: 13 / 13
• Subtask 3: 0 / 27
• Subtask 4: 0 / 49