oj.uz

Submission #1106714

# Submission time Handle Problem Language Result Execution time Memory
1106714 2024-10-31T01:37:37 Z whoknow Džumbus (COCI19_dzumbus) C++17
0 / 110
 1000 ms 2760 KB 
#include <bits/stdc++.h>
#define ll long long
#define F first
#define S second
#define MAXN 1005
#define ii pair<int,int>
#define bit(i,j) ((i>>j)&1)
#define sz(i) (int)i.size()
#define endl '\n'
using namespace std;
const ll INF = 1e18;
int n, m, ntest;
int a[MAXN];
vector<int>g[MAXN];
namespace sub1
{
bool visited[MAXN];
vector<ll>dp[MAXN][2],res;
vector<ll>combine(vector<ll>x,vector<ll>y )
{
    vector<ll>ans(sz(x)+sz(y)-1,INF);
    for(int i=0;i<sz(x);i++)
        for(int j=0;j<sz(y);j++)
            ans[i+j]=min(ans[i+j],x[i]+y[j]);
    return ans;
}
vector<ll>combine1(vector<ll>x,vector<ll>y )
{
    vector<ll>ans(sz(x)+sz(y)-1,INF);
    for(int i=0;i<sz(x);i++)
        for(int j=0;j<sz(y);j++)
            if(i+j!=1)
                ans[i+j]=min(ans[i+j],x[i]+y[j]);
    return ans;
}
vector<ll>mn(vector<ll> x,vector<ll>y)
{
    if(sz(x)<sz(y))
    {
        for(int i=1;i<sz(x);i++)
            y[i]=min(y[i],x[i]);
        return y;
    }
    for(int i=1;i<sz(y);i++)
        x[i]=min(x[i],y[i]);
    return x;
}
void dfs(int u,int p)
{
//    if(u==10)
//        cout<<"|";
//    if(u==1)
//        cout<<"|";
    visited[u]=1;
    dp[u][0]={0,INF};
    dp[u][1]={INF,a[u]};
    for(int v:g[u])
    {
        if(v==p)
            continue;
        dfs(v,u);
        dp[u][1]=mn(dp[u][1],combine(dp[u][1],dp[v][0]));
        dp[u][1]=mn(dp[u][1],combine(dp[u][1],dp[v][1]));
        dp[u][0]=mn(dp[u][0],combine1(dp[u][0],mn(dp[v][0],dp[v][1])));
        vector<ll>().swap(dp[v][1]);
        vector<ll>().swap(dp[v][0]);
    }
}
int bina(int x)
{
    if(sz(res)<=2)
        return 0;
    int l=2,r=sz(res)-1;
    while(l<r)
    {
        int mid=(l+r+1)/2;
        if(res[mid]<=x)
            l=mid;
        else
            r=mid-1;
    }
    if(res[l]<=x)
        return l;
    return 0;
}
void solve()
{
    for(int i = 1; i <= n; i++)
        if(!visited[i])
        {
            dfs(i, 0);
            res = mn(res, mn(dp[i][0], dp[i][1]));
        }
    while(ntest--)
    {
        int x;
        cin >> x;
        cout<<bina(x)<<endl;
    }
}
}
main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    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;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    cin >> ntest;
    sub1::solve();
}

Compilation message

dzumbus.cpp:102:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  102 | main()
      | ^~~~

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1038 ms 2704 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1038 ms 2704 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1035 ms 2760 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1038 ms 2704 KB Time limit exceeded
2 Halted 0 ms 0 KB -