제출 #1128502

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1128502		12345678	Džumbus (COCI19_dzumbus)	C++20	30 / 110	1097 ms	16192 KiB

dzumbus

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int nx=1e3+5;

ll n, m, u, v, vl[nx], q, vs[nx], dp1[nx][nx], dp2[nx][nx], mx, x, sz[nx];
vector<ll> d[nx];
vector<pair<ll, ll>> ans;

void dfsbuild(int u, int p)
{
    vs[u]=1;
    for (auto v:d[u]) if (v!=p) dfsbuild(v, u);
}

void show(int idx)
{
    cout<<"show "<<idx<<'\n';
    cout<<"idx dp1 : ";
    for (int i=0; i<=n; i++) cout<<(dp1[idx][i]==1e18?-1:dp1[idx][i])<<' ';
    cout<<'\n';
    cout<<"idx dp2 : ";
    for (int i=0; i<=n; i++) cout<<(dp2[idx][i]==1e18?-1:dp2[idx][i])<<' ';
    cout<<'\n';
}

void dfs(int u, int p)
{
    sz[u]=1;
    for (auto v:d[u])
    {
        if (v==p) continue;
        dfs(v, u);
        sz[u]+=sz[v];
        for (int i=sz[u]+sz[v]; i>sz[u]; i--)
        {
            for (int j=0; j<=sz[u]; j++) if (i-j>=0) dp2[u][i]=min({dp2[u][i], dp2[u][j]+dp1[v][i-j], dp2[u][j]+dp2[v][i-j]});
            for (int j=0; j<=sz[u]; j++) if (i-j-1>=0) dp2[u][i]=min(dp2[u][i], dp2[v][i-j-1]+vl[u]+dp1[u][j]);
            for (int j=0; j<=sz[u]; j++) if (i-j-1>=0) dp2[u][i]=min(dp2[u][i], dp2[u][j]+vl[v]+dp1[v][i-j-1]);
            for (int j=0; j<=sz[u]; j++) if (i-j-2>=0) dp2[u][i]=min(dp2[u][i], dp1[v][i-j-2]+vl[u]+vl[v]+dp1[u][j]);
            for (int j=0; j<=sz[u]; j++) if (i-j>=0) dp1[u][i]=min({dp1[u][i], dp1[u][j]+dp1[v][i-j], dp1[u][j]+dp2[v][i-j]});
        }
        for (int i=sz[u]; i>=1; i--)
        {
            for (int j=0; j<=sz[v]; j++) if (i-j>=0) dp2[u][i]=min({dp2[u][i], dp2[u][i-j]+dp1[v][j], dp2[u][i-j]+dp2[v][j]});
            for (int j=0; j<=sz[v]; j++) if (i-j-1>=0) dp2[u][i]=min(dp2[u][i], dp2[v][j]+vl[u]+dp1[u][i-j-1]);
            for (int j=0; j<=sz[v]; j++) if (i-j-1>=0) dp2[u][i]=min(dp2[u][i], dp2[u][i-j-1]+vl[v]+dp1[v][j]);
            for (int j=0; j<=sz[v]-1; j++) if (i-j-2>=0) dp2[u][i]=min(dp2[u][i], dp1[v][j]+vl[u]+vl[v]+dp1[u][i-j-2]);
            for (int j=0; j<=sz[v]; j++) if (i-j>=0) dp1[u][i]=min({dp1[u][i], dp1[u][i-j]+dp1[v][j], dp1[u][i-j]+dp2[v][j]});
        }
    }
}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>m;
    for (int i=1; i<=n; i++) cin>>vl[i];
    vl[0]=1e18;
    for (int i=0; i<m; i++) cin>>u>>v, d[u].push_back(v), d[v].push_back(u);
    for (int i=1; i<=n; i++) if (!vs[i]) d[0].push_back(i), dfsbuild(i, i);
    for (int i=0; i<=n; i++) for (int j=0; j<=n; j++) dp1[i][j]=dp2[i][j]=1e18;
    for (int i=0; i<=n; i++) dp1[i][0]=0;
    dfs(0, 0);
    //show(10);
    for (int i=0; i<=n; i++) ans.push_back({dp1[0][i], i});
    sort(ans.begin(), ans.end());
    for (auto &x:ans) mx=max(mx, x.second), x.second=mx;
    cin>>q;
    while (q--) cin>>x, cout<<prev(upper_bound(ans.begin(), ans.end(), make_pair(x, LLONG_MAX)))->second<<'\n';

}

/*
4 3
1 2 3 2
1 2
2 3
3 4
*/

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