Submission #319481

#	Time	Username	Problem	Language	Result	Execution time	Memory
319481		gustason	Džumbus (COCI19_dzumbus)	C++14	0 / 110	39 ms	2404 KiB

dzumbus

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int maxN = 1005;
struct Q {
    int a, b;
    ll cost;
    bool operator<(Q other) const {
        return cost > other.cost;
    }
};
bool isRelaxed[maxN];
ll dp[maxN], cost[maxN];
vector<int> adj[maxN];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= n; i++) {
        cin >> cost[i];
        dp[i] = 1e9 + 5;
    }

    priority_queue<Q> q;
    for(int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
        q.push({a, b, cost[a] + cost[b]});
    }

    int relaxed = 0;
    while(!q.empty()) {
        Q curr = q.top();
        q.pop();
        if (isRelaxed[curr.a] && isRelaxed[curr.b]) continue;
        int prev = dp[relaxed];
        if (!isRelaxed[curr.a]) {
            relaxed++;
            dp[relaxed] = prev + curr.cost;
            for(int u : adj[curr.a]) {
                if (!isRelaxed[u]) {
                    q.push({curr.a, u, cost[u]});
                }
            }
            isRelaxed[curr.a] = true;
        }
        if (!isRelaxed[curr.b]) {
            relaxed++;
            dp[relaxed] = prev + curr.cost;
            for(int u : adj[curr.b]) {
                if (!isRelaxed[u]) {
                    q.push({curr.b, u, cost[u]});
                }
            }
            isRelaxed[curr.b] = true;
        }
    }

    int qr;
    cin >> qr;
    while(qr--) {
        int S;
        cin >> S;
        int L = 0, R = n;
        int ans = 0;
        while(L <= R) {
            int mid = (L + R) / 2;
            if (dp[mid] <= S) {
                L = mid + 1;
                ans = mid;
            } else {
                R = mid - 1;
            }
        }
        cout << ans << "\n";
    }
    return 0;
}
//~ check for overflows

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