Submission #782958

#	Time	Username	Problem	Language	Result	Execution time	Memory
782958		serifefedartar	Džumbus (COCI19_dzumbus)	C++17	0 / 110	233 ms	2336 KiB

dzumbus

#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
• Subtask 2: 0 / 30
• Subtask 3: 0 / 30
• Subtask 4: 0 / 30