oj.uz

Submission #922850

# Submission time Handle Problem Language Result Execution time Memory
922850 2024-02-06T08:07:35 Z Ahmed57 Džumbus (COCI19_dzumbus) C++17
30 / 110
 321 ms 3124 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
int dp[101][101][2][2];
long long a[101];
int vis[101];
vector<int> adj[101];
// 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){
    for(int j = 0;j<=100;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[101][2][2];
        for(int j = 0;j<=100;j++){
            dp2[j][0][0] = dp2[j][1][0] = dp2[j][0][1] = dp2[j][1][1] = 1000000000000000000;
        }
        for(int j = 0;j<=100;j++){
            for(int ch = 0;ch<2;ch++){
                for(int ze = 0;ze<2;ze++){
                    for(int j2 = 0;j2<=100;j2++){
                        for(int ch2 = 0;ch2<2;ch2++){
                            for(int ze2 = 0;ze2<2;ze2++){
                                if((ch==0&&ch2&&ze2==0)||j+j2>100)continue;
                                dp2[j+j2][ch][ze|ch2] = min(dp2[j+j2][ch][ze|ch2],dp[i][j][ch][ze]+dp[q][j2][ch2][ze2]);
                            }
                        }
                    }
                }
            }
        }
        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<=100;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
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 488 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 488 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 283 ms 2896 KB Output is correct
2 Correct 299 ms 2580 KB Output is correct
3 Correct 321 ms 3124 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 488 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -