Submission #1290954

#	Time	Username	Problem	Language	Result	Execution time	Memory
1290954		quan606303	Džumbus (COCI19_dzumbus)	C++20	110 / 110	43 ms	19980 KiB

dzumbus

/*
 * @Author: RMQuan 
 * @Date: 2025-11-14 19:02:30 
 * @Last Modified by: RMQuan
 * @Last Modified time: 2025-11-14 21:39:37
 */
/*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);
    for (auto v:adj[u])
    {
        if (v==p||vst[v])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]);
    }
}      
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.push_back(0);
    for (int i=1;i<=n;i++)
    {
        if (!vst[i])
        {
            dfs(i,0);
            vector<int> n1=Merge1(ans,dp[i][0]);
            vector<int> n2=Merge1(ans,dp[i][1]);
            vector<int> n3=Merge1(ans,dp[i][2]);
            ans.assign(max({n1.size(),n2.size(),n3.size()}),inf);
            for (int j=0;j<n1.size();j++)ans[j]=min(ans[j],n1[j]);
            for (int j=0;j<n2.size();j++)ans[j]=min(ans[j],n2[j]);
            for (int j=0;j<n3.size();j++)ans[j]=min(ans[j],n3[j]);
        }
    }
    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:100:5: note: in expansion of macro 'file'
  100 |     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:100:5: note: in expansion of macro 'file'
  100 |     file();
      |     ^~~~

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