oj.uz

Submission #704815

# Submission time Handle Problem Language Result Execution time Memory
704815 2023-03-03T04:22:33 Z pcc Džumbus (COCI19_dzumbus) C++14
110 / 110
 49 ms 17820 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pll pair<ll,ll>
#define fs first
#define sc second
const int mxn = 1010;
const ll inf = 1e9+10;
vector<int> tree[mxn];
ll dp[mxn][mxn][2];
ll arr[mxn];
int par[mxn];
int sz[mxn];
int n,m;

void init(int now){
    for(auto nxt:tree[now]){
        if(nxt == par[now])continue;
        par[nxt] = now;
        init(nxt);
    }
    return;
}
void dfs(int now){
    sz[now] = 1;
    for(auto &i:dp[now]){
        for(auto &j:i)j = inf;
    }
    dp[now][0][0] = 0;
    sz[now] = 1;
    if(now == 0){
        for(auto nxt:tree[now]){
            if(nxt == par[now])continue;
            dfs(nxt);
            for(int i = sz[now];i>=0;i--){
                for(int j = sz[nxt];j>=0;j--){
                    // cout<<now<<' '<<i<<' '<<j<<' '<<dp[now][i+j][0]<<' '<<dp[now][i][0]<<' '<<min(dp[nxt][j][0],dp[nxt][j][1])<<endl;
                    dp[now][i+j][0] = min({dp[now][i+j][0],dp[now][i][0]+min(dp[nxt][j][0],dp[nxt][j][1])});
                }
            }
            sz[now] += sz[nxt];
        }
        return;
    }
    // dp[now][0][1] = arr[now];
    for(auto nxt:tree[now]){
        if(nxt == par[now])continue;
        dfs(nxt);
        for(int i = sz[now];i>=0;i--){
            for(int j = sz[nxt];j>=0;j--){
                // cout<<now<<" "<<nxt<<' '<<i<<' '<<j<<' '<<dp[now][i][0]<<' '<<dp[now][i][1]<<' '<<dp[nxt][j][0]<<' '<<dp[nxt][j][1]<<endl;
                // dp[now][i+j][1] = min({dp[now][i+j][1],dp[now][i][1]+dp[nxt][j][0]});
                dp[now][i+j+1][1] = min({dp[now][i+j+1][1],dp[now][i][0]+dp[nxt][j][1]+arr[now],dp[now][i][1]+dp[nxt][j][0]+arr[nxt]});
                dp[now][i+j+2][1] = min({dp[now][i+j+2][1],dp[now][i][0]+dp[nxt][j][0]+arr[now]+arr[nxt]});
                dp[now][i+j][0] = min({dp[now][i+j][0],dp[now][i][0]+min(dp[nxt][j][0],dp[nxt][j][1])});
                dp[now][i+j][1] = min({dp[now][i+j][1],dp[now][i][1]+min(dp[nxt][j][1],dp[nxt][j][0])});
            }
        }
        sz[now] += sz[nxt];
    }
    // cout<<now<<":"<<endl;
    // for(int i = 0;i<=20;i++)cout<<dp[now][i][0]<<' ';cout<<endl;
    // for(int i = 0;i<=20;i++)cout<<dp[now][i][1]<<' ';cout<<endl;
    return;
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i = 1;i<=n;i++)cin>>arr[i];
    while(m--){
        int a,b;
        cin>>a>>b;
        tree[a].push_back(b);
        tree[b].push_back(a);
    }
    for(int i = 1;i<=n;i++){
        if(!par[i]){
            init(i);
            tree[0].push_back(i);
        }
    }
    dfs(0);
    vector<pll> v;
    v.push_back({0,0});
    // for(int i = 0;i<20;i++)cout<<dp[0][i][0]<<',';cout<<endl;
    for(int i = 1;i<mxn;i++)if(dp[0][i][0]<inf){
        while(v.back().fs>=dp[0][i][0])v.pop_back();
        v.push_back({dp[0][i][0],i});
    }
    // for(int i = 1;i<=n;i++){
        // cout<<i<<":"<<arr[i]<<'\n';
        // cout<<i<<":"<<sz[i]<<'\n';
    // }
    // for(auto &i:v){
    // 	cout<<i.fs<<":"<<i.sc<<endl;
	// }
    int q;
    cin>>q;
    while(q--){
        ll d;
        cin>>d;
        auto it = --upper_bound(v.begin(),v.end(),make_pair(d+1,-1LL));
        cout<<(*it).second<<'\n';
    }
    return 0;
}

/*
14 13
2 3 4 19 20 21 5 22 6 7 23 8 10 14
1 2
1 3
1 4
2 5
2 6
3 7
3 8
3 9
4 10
8 11
10 13
10 12
12 14
3
45
44
23
*/

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 16344 KB Output is correct
2 Correct 14 ms 16340 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 16344 KB Output is correct
2 Correct 14 ms 16340 KB Output is correct
3 Correct 44 ms 17768 KB Output is correct
4 Correct 43 ms 17820 KB Output is correct
5 Correct 46 ms 17380 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 3396 KB Output is correct
2 Correct 29 ms 3148 KB Output is correct
3 Correct 31 ms 2860 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 16344 KB Output is correct
2 Correct 14 ms 16340 KB Output is correct
3 Correct 44 ms 17768 KB Output is correct
4 Correct 43 ms 17820 KB Output is correct
5 Correct 46 ms 17380 KB Output is correct
6 Correct 28 ms 3396 KB Output is correct
7 Correct 29 ms 3148 KB Output is correct
8 Correct 31 ms 2860 KB Output is correct
9 Correct 38 ms 17548 KB Output is correct
10 Correct 49 ms 17620 KB Output is correct
11 Correct 38 ms 17356 KB Output is correct