oj.uz

Submission #588289

# Submission time Handle Problem Language Result Execution time Memory
588289 2022-07-03T02:21:22 Z Do_you_copy Džumbus (COCI19_dzumbus) C++14
110 / 110
 55 ms 11708 KB 
#include <bits/stdc++.h>
#define taskname "test"
#define fi first
#define se second
#define pb push_back
#define faster ios_base::sync_with_stdio(0); cin.tie(0);
using namespace std;

using ll = long long;
using pii = pair <ll, ll>;

ll min(const ll &a, const ll &b){
    return (a < b) ? a : b;
}

ll max(const ll &a, const ll &b){
    return (a > b) ? a : b;
}

const ll Mod = 1000000007;
const ll maxN = 5e3 + 1;
const ll inf = 1e18;
ll n, m;
bool visited[maxN];
vector <ll> dp[maxN][3];
ll a[maxN];

vector <ll> adj[maxN];

void predfs(ll u){
    visited[u] = 1;
    for (const ll &v: adj[u]){
        if (!visited[v]){
            predfs(v);
        }
    }
}

void dfs(ll u, ll p){
    dp[u][0] = {0, inf};
    dp[u][1] = {a[u], inf};
    dp[u][2] = {inf, inf};
    for (const ll &t: adj[u]){
        if (t != p){
            dfs(t, u);
            ll s = dp[u][0].size() + dp[t][0].size() - 1;
            vector <ll> tem0(s, inf);
            vector <ll> tem1(s, inf);
            vector <ll> tem2(s, inf);
            for (ll i = 0; i < dp[u][0].size(); ++i){
                for (ll j = 0; j < dp[t][0].size(); ++j){
                    tem0[i + j] = min(tem0[i + j], dp[u][0][i] + min(dp[t][0][j], min(dp[t][1][j], dp[t][2][j])));
                    tem1[i + j] = min(tem1[i + j], dp[u][1][i] + dp[t][0][j]);
                    tem2[i + j] = min(tem2[i + j], dp[u][2][i] + min(dp[t][2][j], dp[t][0][j]));
                    if (i + j + 1 < tem2.size())
                    tem2[i + j + 1] = min(tem2[i + j + 1], min(dp[u][2][i] + dp[t][1][j], dp[u][1][i] + dp[t][2][j]));
                    if (i + j + 2 < tem2.size())
                    tem2[i + j + 2] = min(tem2[i + j + 2], dp[u][1][i] + dp[t][1][j]);
                }
            }
            dp[u][0] = tem0;
            dp[u][1] = tem1;
            dp[u][2] = tem2;
        }
    }
}

void Init(){
    cin >> n >> m;
    for (ll i = 1; i <= n; ++i) cin >> a[i];
    for (ll i = 1; i <= m; ++i){
        ll u, v;
        cin >> u >> v;
        adj[u].pb(v);
        adj[v].pb(u);
    }
    a[0] = INT_MAX;
    for (ll i = 1; i <= n; ++i){
        if (!visited[i]){
            predfs(i);
            adj[0].pb(i);
        }
    }
    dfs(0, -1);
    for (int i = n - 1; i >= 0; --i){
        dp[0][0][i] = min(dp[0][0][i], dp[0][0][i + 1]);
    }
    ll q; cin >> q; while (q--){
        ll s; cin >> s;
        ll t = upper_bound(dp[0][0].begin() + 2, dp[0][0].end(), s) - dp[0][0].begin() - 1;
        if (t == 1) --t;
        cout << t << "\n";
    }
}

int main(){
    if (fopen(taskname".txt", "r")){
        freopen(taskname".txt", "r", stdin);
        freopen(taskname".out", "w", stdout);
    }
    faster
    //freopen(taskname.inp, "r", stdin)
    //freopen(taskname.out, "w", stdout)
    Init();
}

Compilation message

dzumbus.cpp: In function 'void dfs(ll, ll)':
dzumbus.cpp:50:30: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |             for (ll i = 0; i < dp[u][0].size(); ++i){
      |                            ~~^~~~~~~~~~~~~~~~~
dzumbus.cpp:51:34: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |                 for (ll j = 0; j < dp[t][0].size(); ++j){
      |                                ~~^~~~~~~~~~~~~~~~~
dzumbus.cpp:55:35: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |                     if (i + j + 1 < tem2.size())
      |                         ~~~~~~~~~~^~~~~~~~~~~~~
dzumbus.cpp:57:35: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |                     if (i + j + 2 < tem2.size())
      |                         ~~~~~~~~~~^~~~~~~~~~~~~
dzumbus.cpp: In function 'int main()':
dzumbus.cpp:98:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   98 |         freopen(taskname".txt", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
dzumbus.cpp:99:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   99 |         freopen(taskname".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 7892 KB Output is correct
2 Correct 14 ms 9940 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 7892 KB Output is correct
2 Correct 14 ms 9940 KB Output is correct
3 Correct 46 ms 11708 KB Output is correct
4 Correct 55 ms 11032 KB Output is correct
5 Correct 48 ms 9956 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 1656 KB Output is correct
2 Correct 35 ms 1356 KB Output is correct
3 Correct 40 ms 3208 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 7892 KB Output is correct
2 Correct 14 ms 9940 KB Output is correct
3 Correct 46 ms 11708 KB Output is correct
4 Correct 55 ms 11032 KB Output is correct
5 Correct 48 ms 9956 KB Output is correct
6 Correct 37 ms 1656 KB Output is correct
7 Correct 35 ms 1356 KB Output is correct
8 Correct 40 ms 3208 KB Output is correct
9 Correct 48 ms 3564 KB Output is correct
10 Correct 47 ms 3816 KB Output is correct
11 Correct 45 ms 3492 KB Output is correct