Submission #1106772

#	Time	Username	Problem	Language	Result	Execution time	Memory
1106772		whoknow	Džumbus (COCI19_dzumbus)	C++17	110 / 110	35 ms	3428 KiB

dzumbus

#include <bits/stdc++.h>
#define ll long long
#define int long long
#define F first
#define S second
#define MAXN 1005
#define ii pair<ll,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
{
int kq[MAXN];
bool visited[MAXN];
vector<ll>dp[MAXN][3], res;
vector<ii>ans;
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>mn(vector<ll> x, vector<ll>y)
{
    if(sz(x) < sz(y))
    {
        for(int i = 0; i < sz(x); i++)
            y[i] = min(y[i], x[i]);
        return y;
    }
    for(int i = 0; i < sz(y); i++)
        x[i] = min(x[i], y[i]);
    return x;
}
void dfs(int u)
{
//    if(u == 6)
//        cout << "|";
    visited[u] = 1;
    dp[u][0] = {0};
    dp[u][1] = {INF, a[u]};
    for(int v : g[u])
    {
        if(visited[v])
            continue;
        dfs(v);
        vector<ll>X = mn(dp[v][0], dp[v][2]);
        dp[u][0] = combine(dp[u][0], X);
        dp[u][2] = mn(combine(dp[u][2], mn(X, dp[v][1])), combine(dp[u][1], mn(dp[v][1], dp[v][2])));
        dp[u][1] = combine(dp[u][1], dp[v][0]);
        vector<ll>().swap(dp[v][0]);
        vector<ll>().swap(dp[v][1]);
        vector<ll>().swap(dp[v][2]);
    }
}
int bina(int x)
{
    if(!sz(ans))
        return -1;
    int l = 0, r = sz(ans) - 1;
    while(l < r)
    {
        int mid = (l + r + 1) / 2;
        if(ans[mid].F <= x)
            l = mid;
        else
            r = mid - 1;
    }
    if(ans[l].F <= x)
        return l;
    return -1;
}
void solve()
{
    for(int i = 1; i <= n; i++)
        if(!visited[i])
        {
            dfs(i);
            if(sz(res))
                res=combine(res,mn(dp[i][0],dp[i][2]));
            else
                res = mn(dp[i][0], dp[i][2]);
        }
    for(int i = 2; i < sz(res); i++)
        ans.push_back({res[i], i});
    sort(ans.begin(), ans.end());
    if(sz(ans))
    {
        kq[1] = ans[0].S;
        for(int i = 1; i <= sz(ans); i++)
            kq[i] = max(kq[i - 1], ans[i - 1].S);
    }
    while(ntest--)
    {
        int x;
        cin >> x;
        cout << kq[bina(x) + 1] << endl;
    }
}
}
main()
{
    if(fopen("TEST.inp", "r"))
    {
        freopen("TEST.inp", "r", stdin);
        freopen("TEST.out", "w", stdout);
    }
    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 (stderr)

dzumbus.cpp:108:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  108 | main()
      | ^~~~
dzumbus.cpp: In function 'int main()':
dzumbus.cpp:112:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  112 |         freopen("TEST.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
dzumbus.cpp:113:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  113 |         freopen("TEST.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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