oj.uz

Submission #988752

# Submission time Handle Problem Language Result Execution time Memory
988752 2024-05-25T22:46:10 Z noyancanturk Džumbus (COCI19_dzumbus) C++17
110 / 110
 43 ms 30892 KB 
#include "bits/stdc++.h"
using namespace std;
    
#define int int64_t
#define pb push_back
    
const int lim=1100;
const int mod=1e9+7;
    
using pii=pair<int,int>;

int a[lim],sz[lim];
int dp[3][lim][lim];
vector<int>v[lim];

void dfs(int node){
    sz[node]=1;
    for(int i=0;i<lim;i++){
        dp[0][node][i]=dp[1][node][i]=dp[2][node][i]=LLONG_MAX/20;
    }
    dp[0][node][0]=0;
    dp[1][node][0]=a[node];
    for(int ch:v[node]){
        if(sz[ch])continue;
        dfs(ch);
        for(int i=sz[node];0<=i;i--){
            for(int j=0;j<=sz[ch];j++){
                dp[0][node][i+j]=min(dp[0][node][i+j],dp[0][node][i]+min({dp[0][ch][j],dp[1][ch][j],dp[2][ch][j]}));
                dp[1][node][i+j]=min(dp[1][node][i+j],dp[1][node][i]+dp[0][ch][j]);
                dp[2][node][i+j]=min(dp[2][node][i+j],dp[2][node][i]+min({dp[0][ch][j],dp[2][ch][j]}));
                dp[2][node][i+j+1]=min({dp[2][node][i+j+1],dp[2][node][i]+dp[1][ch][j],dp[1][node][i]+dp[2][ch][j]});
                dp[2][node][i+j+2]=min(dp[2][node][i+j+2],dp[1][node][i]+dp[1][ch][j]);
            }
        }
        sz[node]+=sz[ch];
    }
}

signed main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#ifdef Local  
    freopen(".in","r",stdin);freopen(".out","w",stdout);
#endif
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=0;i<m;i++){
        int x,y;
        cin>>x>>y;
        v[x].pb(y);
        v[y].pb(x);
    }
    vector<int>roots;
    for(int i=1;i<=n;i++){
        if(!sz[i]){
            dfs(i);
            roots.pb(i);
        }
    }
    sz[0]=1;
    for(int i=0;i<=n;i++){
        dp[0][0][i]=LLONG_MAX/10;
    }
    dp[0][0][0]=0;
    for(int ch:roots){
        for(int i=sz[0];0<=i;i--){
            for(int j=0;j<=sz[ch];j++){
                dp[0][0][i+j]=min(dp[0][0][i+j],dp[0][0][i]+min({dp[0][ch][j],dp[1][ch][j],dp[2][ch][j]}));
            }
        }
        sz[0]+=sz[ch];
    }
    for(int i=n-1;0<=i;i--){
        dp[0][0][i]=min(dp[0][0][i],dp[0][0][i+1]);
    }
    int q;
    cin>>q;
    while(q--){
        int x;
        cin>>x;
        int l=1,r=n,ans=0;
        while(l<=r){
            int mid=(l+r)>>1;
            if(dp[0][0][mid]<=x){
                ans=mid;
                l=mid+1;
            }else{
                r=mid-1;
            }
        }
        cout<<ans<<"\n";
    }
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 27992 KB Output is correct
2 Correct 12 ms 27996 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 27992 KB Output is correct
2 Correct 12 ms 27996 KB Output is correct
3 Correct 35 ms 30148 KB Output is correct
4 Correct 38 ms 30800 KB Output is correct
5 Correct 43 ms 30548 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 8788 KB Output is correct
2 Correct 25 ms 8532 KB Output is correct
3 Correct 27 ms 9044 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 27992 KB Output is correct
2 Correct 12 ms 27996 KB Output is correct
3 Correct 35 ms 30148 KB Output is correct
4 Correct 38 ms 30800 KB Output is correct
5 Correct 43 ms 30548 KB Output is correct
6 Correct 24 ms 8788 KB Output is correct
7 Correct 25 ms 8532 KB Output is correct
8 Correct 27 ms 9044 KB Output is correct
9 Correct 33 ms 30036 KB Output is correct
10 Correct 41 ms 30892 KB Output is correct
11 Correct 38 ms 30548 KB Output is correct