oj.uz

Submission #1106769

# Submission time Handle Problem Language Result Execution time Memory
1106769 2024-10-31T03:26:53 Z whoknow Džumbus (COCI19_dzumbus) C++17
0 / 110
 32 ms 11088 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][3], 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>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)
{
    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]);
    }
}
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);
            res = mn(res, mn(dp[i][0],dp[i][2]));
        }
    while(ntest--)
    {
        int x;
        cin >> x;
        cout << bina(x) << 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:88:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   88 | main()
      | ^~~~
dzumbus.cpp: In function 'int main()':
dzumbus.cpp:92:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   92 |         freopen("TEST.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
dzumbus.cpp:93:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   93 |         freopen("TEST.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 8016 KB Output is correct
2 Incorrect 11 ms 11088 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 8016 KB Output is correct
2 Incorrect 11 ms 11088 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 2640 KB Output is correct
2 Incorrect 32 ms 2412 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 8016 KB Output is correct
2 Incorrect 11 ms 11088 KB Output isn't correct
3 Halted 0 ms 0 KB -