oj.uz

Submission #1106390

# Submission time Handle Problem Language Result Execution time Memory
1106390 2024-10-30T08:41:43 Z Zero_OP Džumbus (COCI19_dzumbus) C++14
110 / 110
 45 ms 19276 KB 
#include <bits/stdc++.h>

using namespace std;

template<typename T>
    bool minimize(T& a, const T& b){
        if(a > b){
            return a = b, true;
        } return false;
    }

struct DisjointSet{
    vector<int> lab;
    DisjointSet(int n) : lab(n, -1) {}

    int root(int u){
        return lab[u] < 0 ? u : (lab[u] = root(lab[u]));
    }

    bool join(int u, int v){
        u = root(u);
        v = root(v);
        if(u == v) return false;
        if(lab[u] > lab[v]) swap(u, v);
        lab[u] += lab[v]; lab[v] = u;
        return true;
    }
};
const long long inf = 1e18;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int N, M;
    cin >> N >> M;
    vector<int> D(N + 1, inf);
    for(int i = 1; i <= N; ++i){
        cin >> D[i];
    }

    vector<vector<int>> adj(N + 1);
    DisjointSet dsu(N + 1);
    while(M--){
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
        dsu.join(u, v);
    }

    for(int i = 1; i <= N; ++i){
        if(dsu.root(i) == i){
            adj[0].push_back(i);
        }
    }

    vector<vector<long long>> f(N + 1, vector<long long>(N + 3, inf));
    vector<vector<long long>> g(N + 1, vector<long long>(N + 3, inf));
    vector<int> sz(N + 1);

    function<void(int, int)> dfs = [&](int u, int p){
        f[u][0] = 0; //not pick u and i
        g[u][1] = D[u]; //pick u and i - 1

        sz[u] = (u > 0);
        for(int v : adj[u]) if(v != p){
            dfs(v, u);

            for(int i = sz[u]; i >= 0; --i){
                for(int j = sz[v]; j >= 0; --j){
                    if(j > 1) minimize(f[u][i + j], f[u][i] + g[v][j]);
                    if(i > 1) minimize(g[u][i + j], g[u][i] + f[v][j]);
                    minimize(f[u][i + j], f[u][i] + f[v][j]);
                    minimize(g[u][i + j], g[u][i] + g[v][j]);
                    minimize(g[u][i + j + 1], f[u][i] + g[v][j] + D[u]);
                    minimize(g[u][i + j + 1], g[u][i] + f[v][j] + D[v]);
                    minimize(g[u][i + j + 2], f[u][i] + f[v][j] + D[u] + D[v]);
                }
            }

            sz[u] += sz[v];
        }
    };

    dfs(0, -1);

    vector<long long> pref(N + 1, 0);
    for(int i = 1; i <= N; ++i){
        pref[i] = f[0][i];
    }

    for(int i = N - 1; i >= 1; --i){
        minimize(pref[i], pref[i + 1]);
    }

    assert(is_sorted(pref.begin(), pref.end()));

    int Q;
    cin >> Q;
    while(Q--){
        long long S;
        cin >> S;
        cout << upper_bound(pref.begin(), pref.end(), S) - pref.begin() - 1 << '\n';
    }

    return 0;
}

Compilation message

dzumbus.cpp: In function 'int main()':
dzumbus.cpp:37:26: warning: overflow in conversion from 'long long int' to 'std::vector<int>::value_type' {aka 'int'} changes value from '1000000000000000000' to '-1486618624' [-Woverflow]
   37 |     vector<int> D(N + 1, inf);
      |                          ^~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 16372 KB Output is correct
2 Correct 14 ms 16464 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 16372 KB Output is correct
2 Correct 14 ms 16464 KB Output is correct
3 Correct 45 ms 18504 KB Output is correct
4 Correct 41 ms 19276 KB Output is correct
5 Correct 40 ms 18772 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 1408 KB Output is correct
2 Correct 21 ms 2484 KB Output is correct
3 Correct 23 ms 2896 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 16372 KB Output is correct
2 Correct 14 ms 16464 KB Output is correct
3 Correct 45 ms 18504 KB Output is correct
4 Correct 41 ms 19276 KB Output is correct
5 Correct 40 ms 18772 KB Output is correct
6 Correct 20 ms 1408 KB Output is correct
7 Correct 21 ms 2484 KB Output is correct
8 Correct 23 ms 2896 KB Output is correct
9 Correct 33 ms 18248 KB Output is correct
10 Correct 38 ms 18968 KB Output is correct
11 Correct 36 ms 18608 KB Output is correct