Submission #922854

#	Time	Username	Problem	Language	Result	Execution time	Memory
922854		Ahmed57	Džumbus (COCI19_dzumbus)	C++17	110 / 110	564 ms	59788 KiB

dzumbus

#include <bits/stdc++.h>
using namespace std;
#define int long long
int dp[1001][1001][2][2];
long long a[1001];int sz[1001];
int vis[1001];
vector<int> adj[1001];
// node i , num of friends , taked or not , is one of children taked or not
void comp(int i){
    vis[i] = 1;
    for(auto j:adj[i]){
        if(vis[j])continue;
        comp(j);
    }
}
void dfs(int i,int pr){
    sz[i] = 1;
    for(int j = 0;j<=1000;j++){
        for(int ch = 0;ch<2;ch++){
            for(int ze = 0;ze<2;ze++){
                if(ch!=j||ze){
                    dp[i][j][ch][ze] = 1e18;
                }else {
                    dp[i][j][ch][ze] = (ch?a[i]:0);
                }
            }
        }
    }
    for(auto q:adj[i]){
        if(q==pr)continue;
        dfs(q,i);
        int dp2[1001][2][2];
        for(int j = 0;j<=1000;j++){
            dp2[j][0][0] = dp2[j][1][0] = dp2[j][0][1] = dp2[j][1][1] = 1000000000000000000;
        }
        for(int j = 0;j<=sz[i];j++){
            for(int ch = 0;ch<2;ch++){
                for(int ze = 0;ze<2;ze++){
                    for(int j2 = 0;j2<=sz[q];j2++){
                        for(int ch2 = 0;ch2<2;ch2++){
                            for(int ze2 = 0;ze2<2;ze2++){
                                if((ch==0&&ch2&&ze2==0)||j+j2>1000)continue;
                                dp2[j+j2][ch][ze|ch2] = min(dp2[j+j2][ch][ze|ch2],dp[i][j][ch][ze]+dp[q][j2][ch2][ze2]);
                            }
                        }
                    }
                }
            }
        }
        sz[i]+=sz[q];
        swap(dp[i],dp2);
    }
}
signed main(){
    ios_base::sync_with_stdio(false);cin.tie(0);
    //freopen("input.txt","r",stdin);
    //freopen("outout.txt","w",stdout);
    int n,m;cin>>n>>m;
    a[0] = 1e18;
    for(int i = 1;i<=n;i++){
        cin>>a[i];
    }
    for(int i = 0;i<m;i++){
        int a,b;cin>>a>>b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    for(int i = 1;i<=n;i++){
        if(!vis[i]){
            comp(i);
            adj[0].push_back(i);
        }
    }
    
    dfs(0,0);
    int q;cin>>q;
    while(q--){
        int s;cin>>s;
        int ma = 0;
        for(int j = 0;j<=1000;j++){
            for(int ch = 0;ch<2;ch++){
                for(int ze = (ch);ze<2;ze++){
                    if(s>=dp[0][j][ch][ze]){
                        ma = j;
                    }
                }
            }
        }
        cout<<ma<<endl;
    }
}

• Subtask 1: 20 / 20
• Subtask 2: 30 / 30
• Subtask 3: 30 / 30
• Subtask 4: 30 / 30