Submission #253604

#	Time	Username	Problem	Language	Result	Execution time	Memory
253604		egekabas	Džumbus (COCI19_dzumbus)	C++14	0 / 110	487 ms	2692 KiB

dzumbus

#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pull;
typedef pair<ll, ll> pii;
typedef pair<ld, ld> pld;
ll n, m;
ll val[1009];
vector<ll> g[1009];
set<pair<ll, pll>> doubles;
set<pll> singles;
ll vis[1009];
ll friends[1009];
pii pr(ll x, ll y){return {min(x, y), max(x, y)};}
ll curans = 0;
ll curused = 0;
vector<pll> v;
vector<pll> sing;
void add(ll x){
    singles.erase({val[x], x});
    ++curans;
    vis[x] = 1;


    for(auto u : g[x]){
        if(vis[u] == 0){
            doubles.erase({{val[u]+val[x]}, pr(x, u)});
            singles.insert({val[u], u});
            friends[u]++;
        }
    }

}
void del(ll x){
    --curans;
    vis[x] = 0;
    ll edge = 0;
    for(auto u : g[x]){
        if(vis[u] == 0){
            friends[u]--;
            if(friends[u] == 0)
                singles.erase({val[u], u});
            doubles.insert({{val[u]+val[x]}, pr(x, u)});
        }
        else
            edge = 1;
    }
    if(edge)
        singles.insert({val[x], x});
}
int main(){
    //ios_base::sync_with_stdio(false);
    //cin.tie(nullptr);
    
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
    
    cin >> n >> m;
    for(ll i = 1; i <= n; ++i)
        cin >> val[i];
    for(ll i = 0; i < m; ++i){
        ll x, y;
        cin >> x >> y;
        g[x].pb(y);
        g[y].pb(x);
        doubles.insert({val[x]+val[y], pr(x, y)});
    }
    while(curans != n){
        if(doubles.size()){
            ll othval = 0;
            if(singles.empty()) othval = 3e9;
            else othval = singles.begin()->ff;
            if(sing.size())
                othval += sing.back().ff;;
            if(othval > doubles.begin()->ff){
                
                if(sing.size()){
                    curused -= sing.back().ff;
                    del(sing.back().ss);
                    sing.pop_back();
                }
                curused += doubles.begin()->ff;
                int x = doubles.begin()->ss.ff;
                int y = doubles.begin()->ss.ss; 
                add(x);
                add(y);
            }
            else{
                sing.pb(*singles.begin());
                curused += singles.begin()->ff;
                add(singles.begin()->ss);
            }
        }
        else{
            sing.pb(*singles.begin());
            curused += singles.begin()->ff;
            add(singles.begin()->ss);
        }
        v.pb({curused, curans});
    }
    ll q;
    cin >> q;
    while(q--){
        ll x;
        cin >> x;
        ll it = upper_bound(v.begin(), v.end(), pll(x, 1e18))-v.begin();
        if(it == 0)
            cout << "0\n";
        else
            cout << v[it-1].ss << '\n';
    }
}

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