#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';
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
512 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
512 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
487 ms |
2692 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
512 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
