Submission #1137428

#	Time	Username	Problem	Language	Result	Execution time	Memory
1137428		monaxia	Džumbus (COCI19_dzumbus)	C++20	0 / 110	16 ms	836 KiB

dzumbus

#include <bits/stdc++.h>
#define pb push_back
#define ppb pop_back
#define fr first
#define sc second
#define all(v) v.begin(), v.end()
#define mod (long long)(1e9 + 7)
#define eps (long long)(1e-9)
#define vektor vector
using namespace std;
 
using ll = long long;
using ull = unsigned long long;
using ld = long double;
 
const ull Mod = 1e9 + 7;
const ll LIMIT = 2e5;

struct edge{
    ll val, u, v;
};

void solve(){
    ll n, m, cur = 0;
    cin >> n >> m;

    vector <vector <ll>> graph(n + 1);
    vector <ll> val(n + 1), visit(n + 1, 0), ans(1, 0);

    auto cmp = [](edge a, edge b){
        return a.val < b.val;
    };

    set <edge, decltype(cmp)> s(cmp);

    for(ll i = 1; i <= n; i ++) cin >> val[i];

    for(ll i = 1; i <= m; i ++){
        ll u, v;
        cin >> u >> v;

        graph[u].pb(v);
        graph[v].pb(u);

        s.insert({val[v] + val[u], u, v});
        s.insert({val[v] + val[u], v, u});
    }

    while(!s.empty()){
        auto it = s.begin();
        ll value = (it -> val), u = (it -> u), v = (it -> v);

        s.erase({value, u, v});
        s.erase({value, v, u});

        if(!visit[u] && !visit[v]){
            cur += val[u] + val[v];
            ans.pb(cur);
            ans.pb(cur);

            visit[u] = visit[v] = 1;

            for(auto& x : graph[u]){
                if(visit[x]) continue;

                s.erase({val[x] + val[u], x, u});
                s.erase({val[x] + val[u], u, x});

                s.insert({val[x], x, u});
                s.insert({val[x], u, x});
            }

            for(auto& x : graph[v]){
                if(visit[x]) continue;

                s.erase({val[x] + val[v], x, v});
                s.erase({val[x] + val[v], v, x});

                s.insert({val[x], x, v});
                s.insert({val[x], v, x});
            }

            continue;
        }

        if(visit[u]) swap(u, v);
        cur += val[u];  
        visit[u] = 1;

        ans.pb(cur);

        for(auto& x : graph[u]){
            if(visit[x]) continue;

            s.erase({val[x] + val[u], x, u});
            s.erase({val[x] + val[u], u, x});

            s.insert({val[x], x, u});
            s.insert({val[x], u, x});
        }
    }

    int q;
    cin >> q;

    while(q --){
        int x;
        cin >> x;

        cout << upper_bound(all(ans), x) - ans.begin() - 1 << "\n";
    }
}

 
signed main()
{
    cin.tie(0)->sync_with_stdio(0);
 
    // if(fopen("nameholder.inp", "r")){
    //     freopen("nameholder.inp", "r", stdin);
    //     freopen("nameholder.out", "w", stdout);
    // }
    
    // cout << 1; return 0;
 
    ll n = 1;
 
    // cin >> n;
 
    while(n) {
        solve();
        n --;
        cout << "\n";
    }
 
    // cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
    return 0;
}
 
//                                   ++++                                           
//                          ++++-::......:--:::-=+++                                
//                    ++++=:............---.....--:..:=++++++                       
//                    +++++++::......................::=+++++                       
//             @@               ++++++++++:+++++++++                                
//             @%                                  @*                               
//              %%@@                    *****#*@@                                   
//             %%%%%                  @##**##***%                                   
//           @@@@@@+-*#*@             #####%+*##*@                                  
//                  %#+@%%@@@         ##-%:::-#*###@@                               
//                 =====:*:::        ###-:==::=#*%*                                 
//                    -====:::::+@@%@@%@#*--=*#%%#@%@   @%@                         
//                        @=====%=-@%=:::.:+-::::+::::::::::::%-----%% @@@@@        
//                        @@%#*@++%===+::-================@%@@@@+++++++@@@%%%@#%###%
//               @#***#@@   @##=%@===+--:+==+===+%*##@%%%@@@@@@@@@@:=  @%@%%%@#%%   
//    -@      @*#@         #####%:::-====+:::==---**%#@ *%%%%@@@@@@-:               
//    -=-*%  #          #***--%%::::::::+=-+#-----=**@*#     #+**#@#                
//     ----=----#+****=----=*#@=::::::=#-----------***%*%                           
//      ------------%*****##=@==::::::+%-----------***%**                           
//       +-----------------*@++%::::::::-----------****@*#                          
//         =------------% @%=+%#+:::::::* #-----*--**** **                          
//            ----%--%    *==+++++=+=##*:%   ---=--**** **                          
//                       %@@@@@@@@@==@+%%%%@   ----**** *#                          
//                     @=*+%@@@%@@=++=:%:::%      #***@@#                           
//                    #+++++++++#==++-::::::     @**** *#                           
//                   =+++++++++++==+++:::::::   ####@ #%                            
//                  +++++++++++=@ @++++::::::@      @#                              
//                 @+++++++++=@    =*++=:::::@                                      
//                 ++++++++@       @++++:::::                                       
//                ++++++=           =++++:::                                        
//               =+++++@             =+++::::                                       
//             ++++++-@               =+++:+::                                      
//           @::+::::@                 =++::-:::                                    
//          +::=:::::                  @+*+:-+++-:                                  
//        @::+-:::::#                     +++::::::@                                
//       ::%=:::::::%@                    @%++::::***                               
//     @:+@*:::::::****@                   +@+++:-=*:*@                             
//    *:@@%::::::::=****                   @%@+++:::#**@                            
//   *%@@@-:::::::%=+==*@                   +@%+++:***+*                            
//  #%@@%%::::::::#+=-=#                    =+@+++++:::*+                           
// @####+::::::::%+=@#%#=@                  @**@@%=++::::@                          
// @   +:::::::::***#*@ @@###+=+=%@          +**#+=+*+:::-                          
//    =-:::::::%%%%@@          @#=*########%#+*%%+--@*+::%                          
//   +---%@                                   @@ =-:-**:#                           
//  %%%%%                                        @+--*@                             
// @%%%%@                                        @%%%%%                             
//                                                @%%@@

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