Submission #1290949

#	Time	Username	Problem	Language	Result	Execution time	Memory
1290949		quan606303	Džumbus (COCI19_dzumbus)	C++20	50 / 110	51 ms	20872 KiB

dzumbus

/*
 * @Author: RMQuan 
 * @Date: 2025-11-14 19:02:30 
 * @Last Modified by: RMQuan
 * @Last Modified time: 2025-11-14 21:19:40
 */
/*idea : 
    goi dp[u][0] la khi goc u cac cay con lien tiep noi voi u=0 (tinh ca u)
    goi dp[u][1] la khi goc u cac cay con lien tiep noi voi u=1 (tinh ca u)
    goi dp[u][2] la khi goc u cac cay con lien tiep noi voi u>=2(tinh ca u)                 
    voi index ben trong la so cap toi thieu  
*/
#include <bits/stdc++.h>
bool M1;
#define int long long
#define ll long long
#define INTMAX INT_MAX
#define INTMIN INT_MIN
#define LONGMAX LLONG_MAX
#define LONGMIN LLONG_MIN
#define fi first
#define se second
#define memfull(a,b) memset(a,b,sizeof(a));
#define endl '\n'
#define TASK "TEST"
#define file() if (fopen(TASK".inp","r")){freopen(TASK".inp","r",stdin); freopen(TASK".out","w",stdout);}
using namespace std;
const int MOD=1e9+7;
const int maxn=1e5+7;
const int inf=1e18;
int n,q,a[maxn],m;
bool vst[maxn];
vector<int> dp[maxn][3];
vector<int> adj[maxn];
vector<int> Merge1(const vector<int> &a,const vector<int> &b)
{
    vector<int> c(a.size()+b.size(),inf);
    for (int i=0;i<a.size();i++)
    {
        for (int j=0;j<b.size();j++)c[i+j]=min(c[i+j],a[i]+b[j]);
    }
    return c;
}
vector<int> Merge2(const vector<int> &a,const vector<int> &b)
{
    vector<int> c(a.size()+b.size()+1,inf);
    for (int i=0;i<a.size();i++)
    {
        for (int j=0;j<b.size();j++)c[i+j+1]=min(c[i+j+1],a[i]+b[j]);
    }
    return c;
}
vector<int> Merge3(const vector<int> &a,const vector<int> &b)
{
    vector<int> c(a.size()+b.size()+2,inf);
    for (int i=0;i<a.size();i++)
    {
        for (int j=0;j<b.size();j++)c[i+j+2]=min(c[i+j+2],a[i]+b[j]);
    }
    return c;
}
vector<int> ans;
void dfs(int u,int p)
{
    vst[u]=true;
    dp[u][0].push_back(0);
    dp[u][1].push_back(a[u]);
    dp[u][2].push_back(inf);
   // cerr<<"vst : "<<u<<endl;
    for (auto v:adj[u])
    {
        if (v==p)continue;
        dfs(v,u); 
        vector<int> n1=Merge1(dp[u][0],dp[v][0]);
        vector<int> n2=Merge1(dp[u][0],dp[v][1]);
        vector<int> n3=Merge1(dp[u][0],dp[v][2]);
        vector<int> n4=Merge1(dp[u][1],dp[v][0]);
        vector<int> n5=Merge1(dp[u][2],dp[v][2]);
        vector<int> n6=Merge2(dp[u][2],dp[v][1]);
        vector<int> n7=Merge1(dp[u][2],dp[v][0]);
        vector<int> n8=Merge3(dp[u][1],dp[v][1]);
        vector<int> n9=Merge2(dp[u][1],dp[v][2]);
        dp[u][0].assign(max({n1.size(),n2.size(),n3.size()}),inf);
        for (int i=0;i<n1.size();i++)dp[u][0][i]=min(dp[u][0][i],n1[i]);
        for (int i=0;i<n2.size();i++)dp[u][0][i]=min(dp[u][0][i],n2[i]);
        for (int i=0;i<n3.size();i++)dp[u][0][i]=min(dp[u][0][i],n3[i]);
        dp[u][1]=n4;
        dp[u][2].assign(max({n5.size(),n6.size(),n7.size(),n8.size(),n9.size()}),inf);
        for (int i=0;i<n5.size();i++)dp[u][2][i]=min(dp[u][2][i],n5[i]);
        for (int i=0;i<n6.size();i++)dp[u][2][i]=min(dp[u][2][i],n6[i]);
        for (int i=0;i<n7.size();i++)dp[u][2][i]=min(dp[u][2][i],n7[i]);
        for (int i=0;i<n8.size();i++)dp[u][2][i]=min(dp[u][2][i],n8[i]);
        for (int i=0;i<n9.size();i++)dp[u][2][i]=min(dp[u][2][i],n9[i]);
    }
  //  cerr<<u<<" : "<<endl;
        //cerr<<"+ 0 :"<<endl;

    for (int i=0;i<dp[u][0].size();i++)
    {
        ans[i]=min(ans[i],dp[u][0][i]);
      //  cerr<<i<<" = "<<dp[u][0][i]<<endl;
    }
 //   cerr<<endl;
           // cerr<<"+ 1:"<<endl;

    for (int i=0;i<dp[u][1].size();i++)
    {
        ans[i]=min(ans[i],dp[u][1][i]);
      //  cerr<<i<<" = "<<dp[u][1][i]<<endl;
    }    
    //cerr<<endl;        
   // cerr<<"+ 2:"<<endl;

    for (int i=0;i<dp[u][2].size();i++)
    {
        ans[i]=min(ans[i],dp[u][2][i]);
        //cerr<<i<<" = "<<dp[u][2][i]<<endl;
    }
        //cerr<<endl;

}      
int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    file();
    cin>>n>>m;
    for (int i=1;i<=n;i++)cin>>a[i];
    for (int i=1;i<=m;i++)
    {
        int x,y;
        cin>>x>>y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    ans.assign(maxn+5,inf);
    for (int i=1;i<=n;i++)if (!vst[i])dfs(i,0);
    for (int i=ans.size()-2;i>=0;i--)ans[i]=min(ans[i],ans[i+1]);
    cin>>q;
    while (q--)
    {
        int x;
        cin>>x;
        int res=(upper_bound(ans.begin(),ans.end(),x)-ans.begin()-1);
        cout<<res<<endl;
    }
    return 0;
}

Compilation message (stderr)

dzumbus.cpp: In function 'int32_t main()':
dzumbus.cpp:26:50: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 | #define file() if (fopen(TASK".inp","r")){freopen(TASK".inp","r",stdin); freopen(TASK".out","w",stdout);}
      |                                           ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
dzumbus.cpp:127:5: note: in expansion of macro 'file'
  127 |     file();
      |     ^~~~
dzumbus.cpp:26:81: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 | #define file() if (fopen(TASK".inp","r")){freopen(TASK".inp","r",stdin); freopen(TASK".out","w",stdout);}
      |                                                                          ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
dzumbus.cpp:127:5: note: in expansion of macro 'file'
  127 |     file();
      |     ^~~~

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