oj.uz

Submission #922854

# Submission time Handle Problem Language Result Execution time Memory
922854 2024-02-06T08:09:57 Z Ahmed57 Džumbus (COCI19_dzumbus) C++17
110 / 110
 564 ms 59788 KB 
#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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 52312 KB Output is correct
2 Correct 46 ms 55900 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 52312 KB Output is correct
2 Correct 46 ms 55900 KB Output is correct
3 Correct 545 ms 59788 KB Output is correct
4 Correct 564 ms 54244 KB Output is correct
5 Correct 519 ms 50180 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 518 ms 6724 KB Output is correct
2 Correct 507 ms 5444 KB Output is correct
3 Correct 500 ms 5180 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 52312 KB Output is correct
2 Correct 46 ms 55900 KB Output is correct
3 Correct 545 ms 59788 KB Output is correct
4 Correct 564 ms 54244 KB Output is correct
5 Correct 519 ms 50180 KB Output is correct
6 Correct 518 ms 6724 KB Output is correct
7 Correct 507 ms 5444 KB Output is correct
8 Correct 500 ms 5180 KB Output is correct
9 Correct 508 ms 36004 KB Output is correct
10 Correct 506 ms 35400 KB Output is correct
11 Correct 512 ms 34764 KB Output is correct