oj.uz

Submission #319481

# Submission time Handle Problem Language Result Execution time Memory
319481 2020-11-05T11:09:11 Z gustason Džumbus (COCI19_dzumbus) C++14
0 / 110
 39 ms 2404 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 492 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 492 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 39 ms 2404 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 492 KB Output isn't correct
2 Halted 0 ms 0 KB -