oj.uz

Submission #782958

# Submission time Handle Problem Language Result Execution time Memory
782958 2023-07-14T12:50:01 Z serifefedartar Džumbus (COCI19_dzumbus) C++17
0 / 110
 233 ms 2336 KB 
#include <bits/stdc++.h>
using namespace std;

#define fast ios::sync_with_stdio(0);cin.tie(0);
typedef long long ll;
#define f first
#define s second
#define MAXN 100005

set<pair<int,pair<int,int>>> edges;
vector<int> D;
int main() {
    fast
    int N, M, u, v;
    cin >> N >> M;

    D = vector<int>(N+1);
    vector<int> taken(N+1, false); 
    for (int i = 1; i <= N; i++)
        cin >> D[i];
    for (int i = 1; i <= M; i++) {
        cin >> u >> v;
        edges.insert({D[u] + D[v], {u, v}});
    }

    vector<pair<int,int>> need;
    need.push_back({0, 0});
    while (edges.size()) {
        int wt = edges.begin()->first;
        int from = edges.begin()->second.first;
        int to = edges.begin()->second.second;
        edges.erase(edges.begin());
        need.push_back({need.back().first + wt, need.back().second + !taken[from] + !taken[to]});
        taken[from] = true;
        taken[to] = true; 
        
        set<pair<int,pair<int,int>>> new_set;
        for (auto u : edges) {
            if (taken[u.second.first] && !taken[u.second.second]) {
                pair<int,pair<int,int>> edge = u;
                new_set.insert({D[u.s.s], {edge.s.f, edge.s.s}});
            } else if (!taken[u.second.first] && taken[u.second.second]) {
                pair<int,pair<int,int>> edge = u;
                new_set.insert({D[u.s.f], {edge.s.f, edge.s.s}});
            } else if (!taken[u.second.first] && !taken[u.second.second])
                new_set.insert(u);
        }

        edges.clear();
        for (auto u : new_set)
            edges.insert(u);
    }

    int Q;
    cin >> Q;
    while (Q--) {
        int k;
        cin >> k;
        int q = upper_bound(need.begin(), need.end(), make_pair(k, INT_MAX)) - need.begin() - 1;
        cout << need[q].second << endl;
    }
}

Subtask #1
0 / 20.0

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

Subtask #2
0 / 30.0

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

Subtask #3
0 / 30.0

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

Subtask #4
0 / 30.0

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