oj.uz

Submission #1106770

# Submission time Handle Problem Language Result Execution time Memory
1106770 2024-10-31T03:45:56 Z whoknow Džumbus (COCI19_dzumbus) C++17
50 / 110
 38 ms 13904 KB 
#include <bits/stdc++.h>
#define ll 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]);
    }
}
int bina(int x)
{
    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);
            res = mn(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());
    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:96:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   96 | main()
      | ^~~~
dzumbus.cpp: In function 'int main()':
dzumbus.cpp:100:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  100 |         freopen("TEST.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
dzumbus.cpp:101:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  101 |         freopen("TEST.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 8016 KB Output is correct
2 Correct 11 ms 11088 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 8016 KB Output is correct
2 Correct 11 ms 11088 KB Output is correct
3 Correct 33 ms 13904 KB Output is correct
4 Correct 38 ms 11592 KB Output is correct
5 Correct 36 ms 10320 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 1360 KB Output is correct
2 Incorrect 20 ms 1104 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 8016 KB Output is correct
2 Correct 11 ms 11088 KB Output is correct
3 Correct 33 ms 13904 KB Output is correct
4 Correct 38 ms 11592 KB Output is correct
5 Correct 36 ms 10320 KB Output is correct
6 Correct 23 ms 1360 KB Output is correct
7 Incorrect 20 ms 1104 KB Output isn't correct
8 Halted 0 ms 0 KB -