Submission #1128664

#	Time	Username	Problem	Language	Result	Execution time	Memory
1128664		trMatherz	Džumbus (COCI19_dzumbus)	C++20	110 / 110	286 ms	16608 KiB

dzumbus

#include <iostream> 
 
 
// #include <fstream>
// std::ifstream cin ("boarding.in");
// std::ofstream cout ("boarding.out");
 
 
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <string>
#include <vector>
#include <array>
#include <algorithm>
#include <numeric>
#include <iomanip>
#include <unordered_set>
#include <stack>
#include <tuple>
#include <ext/pb_ds/assoc_container.hpp>
#include <random>
#include <chrono>
#include <bitset>
#include <complex>
#include <tuple> 
 

using namespace std;
using namespace __gnu_pbds;

 
typedef long long ll;
template <typename T, typename U>
bool emin(T &a, const U &b) { return b < a ? a = b, true : false; }
template <typename T, typename U>
bool emax(T &a, const U &b) { return b > a ? a = b, true : false; }
template <class T> using iset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef uint64_t hash_t;
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
const ll M = (1LL << 61) - 1;
const ll B = uniform_int_distribution<ll>(0, M - 1)(rng);
__int128 mul(ll a, ll b) { return (__int128)a * b; }
__int128 add(ll a, ll b) { return (__int128)a + b; }
ll mod_mul(ll a, ll b) { return mul(a, b) % M; }
ll mod_add(ll a, ll b) { return add(a, b) % M; }

const ll inf = (ll) 1e17 + 7; 
int n, m; 
vector<vector<vector<ll>>> dp;
vector<vector<int>> a; 
vector<ll> v; 
void merge(auto &x, auto y, ll w1, ll w2) {
    vector<vector<ll>> nex(2, vector<ll>(x[0].size() + y[0].size() + 1, inf));
    for(int i = 0; i < x[0].size(); i++) {
        for(int j = 0; j < y[0].size(); j++) {
            emin(nex[0][i + j], x[0][i] + y[0][j]); 
            emin(nex[0][i + j], x[0][i] + y[1][j]); 

            emin(nex[1][i + j], x[1][i] + y[0][j]); 
            emin(nex[1][i + j], x[1][i] + y[1][j]); 

            emin(nex[1][i + j + 1], x[0][i] + y[1][j] + w1); 
            emin(nex[1][i + j + 1], x[1][i] + y[0][j] + w2); 
            emin(nex[1][i + j + 2], x[0][i] + y[0][j] + w1 + w2); 
        }
    }
    swap(nex, x); 
}
void go(int x, int y = -1) {
    if(dp[x].size() != 0) return; 
    dp[x] = { {0}, {inf} };
    for(auto &u : a[x]) {
        if(u == y) continue; 
        go(u, x); 
        merge(dp[x], dp[u], v[x], v[u]); 
    }
}
int main() {
    cin >> n >> m; 
    dp = vector<vector<vector<ll>>>(n);
    a = vector<vector<int>>(n); 
    v = vector<ll>(n); 
    for(auto &u : v) cin >> u; 
    for(int i = 0; i < m; i++) {
        int x, y; 
        cin >> x >> y; 
        x--, y--; 
        a[x].push_back(y), a[y].push_back(x); 
    }
    vector<vector<ll>> ans = { {0}, {inf} }; 
    for(int i = 0; i < n; i++) { 
        if(dp[i].size() != 0) continue; 
        go(i); 
        merge(ans, dp[i], inf, inf); 
    }
    int q; 
    cin >> q; 
    for(int i = 0; i < ans[0].size() - 1; i++) emin(ans[0][i], ans[0][i + 1]); 
    for(int i = 0; i < q; i++) {
        ll x; 
        cin >> x; 
        int l = 0, r = ans[0].size() - 1; 
        while(l < r) {
            int m = (l + r + 1) / 2;
            if(ans[0][m] <= x) l = m; 
            else r = m - 1; 
        }
        cout << l << endl;
    }
}

• Subtask 1: 20 / 20
• Subtask 2: 30 / 30
• Subtask 3: 30 / 30
• Subtask 4: 30 / 30