Submission #1148852

#	Time	Username	Problem	Language	Result	Execution time	Memory
1148852		alir3za_zar3	Džumbus (COCI19_dzumbus)	C++20	110 / 110	117 ms	17224 KiB

dzumbus

// Alir3za.Zar3 -> Shiraz , Iran
#include <bits/stdc++.h>
using namespace std;
#define          int            long long
#define    loop(i , l , r)      for (int i=l; i<=r; i+=1)
#define     arc(i , r , l)      for (int i=r; i>=l; i-=1)
#define     Turbo_In_Out        ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define     Tc_Management       int Tc;cin>>Tc;while(Tc--)
const int N = 1e3+10 , Inf = 1e18;
int n,m,Dzumbus[N],comp[N];
int dp[N][N],pd[N][N],upd[2][N],sz[N];
vector<int> e[N];
void comp_processor (int v , int par)
{   comp[v] = par;
    for (auto to : e[v])
    {   if (to==par){ continue; }
        comp_processor(to,v);
    }
} void Combine (int v , int u)
{   loop(s,0,sz[v]){ loop(z,0,sz[u]){
        upd[0][s+z]=upd[1][s+z]=Inf;
    } }
    loop(s,0,sz[v]){ loop(z,0,sz[u]){
        upd[0][s+z] = min(upd[0][s+z] , dp[v][s]+dp[u][z]);
        if (s>0 and z>0){
            upd[0][s+z] = min(upd[0][s+z] , pd[v][s]+pd[u][z]);
            upd[1][s+z] = min(upd[1][s+z] , pd[v][s]+pd[u][z]);
        } if (s>0)
            upd[1][s+z] = min(upd[1][s+z] , pd[v][s]+dp[u][z]);
        if (z>0)
           upd[1][s+z] = min(upd[1][s+z] , dp[v][s]+pd[u][z]+Dzumbus[v]);
    } }
    loop(s,0,sz[v]){ loop(z,0,sz[u]){
        dp[v][s+z] = min(dp[v][s+z],upd[0][s+z]);
        pd[v][s+z] = min(pd[v][s+z],upd[1][s+z]);
    } }
    sz[v] += sz[u];
} void Combining_DFS (int v , int par)
{   sz[v]=1; dp[v][0]=0; pd[v][1]=Dzumbus[v];
    for (auto to : e[v])
    {   if (to==par){ continue; }
        Combining_DFS(to,v);
        Combine(v,to);
    }
}
signed main(){
    Turbo_In_Out
    cin >> n >> m; loop(i,1,n)
    { cin >> Dzumbus[i]; comp[i]=i; }
    Dzumbus[0] = Inf;
    loop(i,0,N-1){ loop(j,0,N-1){
        dp[i][j]=pd[i][j]=Inf;
    } } loop(i,1,m)
    {   int u,v; cin >> u >> v;
        e[u].push_back(v);
        e[v].push_back(u);
    } loop(v,1,n)
    {   if (comp[v]==v)
        {   comp_processor(v,0);
            e[0].push_back(v);
        }
    } Combining_DFS(0,0);
    int q; cin >> q;
    while (q--)
    {   int S,out; cin >> S;
        arc(k,n,0)
        { if (dp[0][k]<=S){ out=k; break; } }
        cout << out << '\n';
    }
}

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