oj.uz

Submission #1106772

# Submission time Handle Problem Language Result Execution time Memory
1106772 2024-10-31T03:58:10 Z whoknow Džumbus (COCI19_dzumbus) C++17
110 / 110
 35 ms 3428 KB 
#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

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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1360 KB Output is correct
2 Correct 6 ms 1360 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1360 KB Output is correct
2 Correct 6 ms 1360 KB Output is correct
3 Correct 25 ms 2556 KB Output is correct
4 Correct 33 ms 2120 KB Output is correct
5 Correct 29 ms 1616 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 1360 KB Output is correct
2 Correct 20 ms 1104 KB Output is correct
3 Correct 24 ms 2704 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1360 KB Output is correct
2 Correct 6 ms 1360 KB Output is correct
3 Correct 25 ms 2556 KB Output is correct
4 Correct 33 ms 2120 KB Output is correct
5 Correct 29 ms 1616 KB Output is correct
6 Correct 20 ms 1360 KB Output is correct
7 Correct 20 ms 1104 KB Output is correct
8 Correct 24 ms 2704 KB Output is correct
9 Correct 23 ms 2896 KB Output is correct
10 Correct 25 ms 3428 KB Output is correct
11 Correct 35 ms 3148 KB Output is correct