oj.uz

Submission #918876

# Submission time Handle Problem Language Result Execution time Memory
918876 2024-01-30T15:37:56 Z vjudge1 Džumbus (COCI19_dzumbus) C++17
110 / 110
 41 ms 11836 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ld long double
#define ull unsigned long long
#define pii pair<int,int>
#define pll pair<long long, long long>
#define fi first
#define se second
#define all(a) (a).begin(), (a).end()
#define pb push_back
#define lwb lower_bound
#define upb upper_bound

#define TASKNAME "NAME"

void init()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    ///freopen(TASKNAME".INP","r",stdin); freopen(TASKNAME".OUT","w",stdout);
}

const int SZ = 5e3+5;
const ll INF = INT_MAX / 2, MOD = 1e9+7, INFLL = 2e18;
const double epsilon = 1e-3;

int n,m,q;
ll a[SZ];
vector<int> adj[SZ];
bool vis[SZ];
vector<ll> dp[SZ][3];

void preDfs(int u)
{
    vis[u] = true;
    for(int v : adj[u])
    {
        if(vis[v]) continue;
        preDfs(v);
    }
}

void dfs(int u, int pre)
{
    dp[u][0] = {0,INFLL};
    dp[u][1] = {a[u], INFLL};
    dp[u][2] = {INFLL, INFLL};
    for(int v : adj[u])
    {
        if(v == pre) continue;
        dfs(v, u);
        ll s = dp[u][0].size() + dp[v][0].size() - 1;
        vector<ll> t0(s, INFLL), t1(s, INFLL), t2(s, INFLL);
        for(int i = 0; i < dp[u][0].size(); i++)
        {
            for(int j = 0; j < dp[v][0].size(); j++)
            {
                t0[i+j] = min(t0[i+j], dp[u][0][i] + min({ dp[v][0][j], dp[v][1][j], dp[v][2][j] }));
                t1[i+j] = min(t1[i+j], dp[u][1][i] + dp[v][0][j]);
                t2[i+j] = min(t2[i+j], dp[u][2][i] + min(dp[v][2][j], dp[v][0][j]));
                if(i + j + 1 < t2.size()) t2[i + j + 1] = min({ t2[i+j+1], dp[u][2][i] + dp[v][1][j], dp[u][1][i] + dp[v][2][j] });
                if(i + j + 2 < t2.size()) t2[i+j+2] = min(t2[i+j+2], dp[u][1][i] + dp[v][1][j]);
            }
        }
        dp[u][0] = t0;
        dp[u][1] = t1;
        dp[u][2] = t2;
    }
}

int main()
{
    init();
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    for(int i = 1; i <= m; i++)
    {
        int u,v;
        cin >> u >> v;
        adj[u].pb(v);
        adj[v].pb(u);
    }
    a[0] = INFLL;
    for(int i = 1; i <= n; i++)
    {
        if(vis[i]) continue;
        preDfs(i);
        adj[0].pb(i);
    }
    dfs(0,0);
    for (int i = n - 1; i >= 0; --i){
        dp[0][0][i] = min(dp[0][0][i], dp[0][0][i + 1]);
    }
    cin >> q;
    while(q--)
    {
        ll s;
        cin >> s;
        int pos = upb(dp[0][0].begin()+2, dp[0][0].end(),s) - dp[0][0].begin() - 1;
        if(pos == 1) pos--;
        cout << pos << '\n';
    }
}

Compilation message

dzumbus.cpp: In function 'void dfs(int, int)':
dzumbus.cpp:55:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |         for(int i = 0; i < dp[u][0].size(); i++)
      |                        ~~^~~~~~~~~~~~~~~~~
dzumbus.cpp:57:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |             for(int j = 0; j < dp[v][0].size(); j++)
      |                            ~~^~~~~~~~~~~~~~~~~
dzumbus.cpp:62:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |                 if(i + j + 1 < t2.size()) t2[i + j + 1] = min({ t2[i+j+1], dp[u][2][i] + dp[v][1][j], dp[u][1][i] + dp[v][2][j] });
      |                    ~~~~~~~~~~^~~~~~~~~~~
dzumbus.cpp:63:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |                 if(i + j + 2 < t2.size()) t2[i+j+2] = min(t2[i+j+2], dp[u][1][i] + dp[v][1][j]);
      |                    ~~~~~~~~~~^~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 8024 KB Output is correct
2 Correct 9 ms 10276 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 8024 KB Output is correct
2 Correct 9 ms 10276 KB Output is correct
3 Correct 39 ms 11836 KB Output is correct
4 Correct 41 ms 11244 KB Output is correct
5 Correct 38 ms 10064 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 1836 KB Output is correct
2 Correct 27 ms 1368 KB Output is correct
3 Correct 30 ms 1400 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 8024 KB Output is correct
2 Correct 9 ms 10276 KB Output is correct
3 Correct 39 ms 11836 KB Output is correct
4 Correct 41 ms 11244 KB Output is correct
5 Correct 38 ms 10064 KB Output is correct
6 Correct 29 ms 1836 KB Output is correct
7 Correct 27 ms 1368 KB Output is correct
8 Correct 30 ms 1400 KB Output is correct
9 Correct 33 ms 3664 KB Output is correct
10 Correct 39 ms 3920 KB Output is correct
11 Correct 36 ms 3548 KB Output is correct