Submission #1337316

#	Time	Username	Problem	Language	Result	Execution time	Memory
1337316		neptunns	Džumbus (COCI19_dzumbus)	C++20	Evaluating	0 ms	0 KiB

dzumbus

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int long long
#define maxn 1005
#define mi LLONG_MIN
#define ma LLONG_MAX
#define mod 1000000007
#define pb push_back
#define S second
#define F first
vector<int> p(maxn), sz(maxn);
int get(int x) { return (p[x] == x ? p[x] : p[x] = get(p[x])); }
bool merge(int x, int y) {
    x = get(x);
    y = get(y);
    if (x == y) return 0;
    if (sz[x] < sz[y]) swap(x, y);
    sz[x] += sz[y];
    p[y] = x;
    return 1;
}

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

    int n, m;
    cin >> n >> m;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        p[i] = i;
        sz[i] = 1;
    }

    vector<pair<int, pair<int, int>>> g1;
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        u--;
        v--;
        g1.pb({a[v] + a[u], {u, v}});
    }
    vector<int> ans;
    sort(g1.begin(), g1.end());
    int sum = 0;
    ans.pb(sum);
    for (auto it : g1) {
        int w = it.F, u = it.S.F, v = it.S.S;
        if (merge(u, v)) {
            sum += w;
            ans.pb(sum);
        }
    }
    int q;
    cin >> q;

    while (q--) {
        int x;
        cin >> x;
        int cnt;
        if (upper_bound(ans.begin(), ans.end(), x) == ans.end()) {
            cnt = ans.size();
        } else {
            cnt = upper_bound(ans.begin(), ans.end(), x) - ans.begin() - 1;
        }
        cout << cnt * 2 << endl;
    }
}