Submission #345179

#	Time	Username	Problem	Language	Result	Execution time	Memory
345179		limabeans	Džumbus (COCI19_dzumbus)	C++17	0 / 110	57 ms	25932 KiB

dzumbus

#include <bits/stdc++.h>
using namespace std;

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl





using ll = long long;


const int maxn = 1e6 + 5;



int n,m,q;
ll a[maxn];
vector<int> g[maxn];

bool act[maxn];

struct dat {
    vector<int> inds;
    dat(vector<int> w) {
	inds = w;
    }

    ll sum() {
	ll res = 0;
	for (ll i: inds) {
	    res += a[i];
	}
	return res;
    }

    ll size() {
	return inds.size();
    }

    pair<ll,ll> val() const {
	ll cnt = inds.size();
	ll sum = 0;
	for (ll i: inds) {
	    sum += a[i];
	}
	return {sum, cnt};
    }

    bool operator<(const dat& o) const {
	auto cur = val();
	auto them = o.val();
	//return cur.first/cur.second < them.first/them.second;
	if (cur.first*them.second != them.first*cur.second) {
	    return cur.first*them.second < them.first*cur.second;
	}

	return inds < o.inds;
    }

    bool active() {
	for (int i: inds) {
	    if (!act[i]) return false;
	}
	return true;
    }

    void print() {
	for (int i: inds) cout<<i<<",";
	cout<<": ";
	cout<<sum()<<endl;
    }
};

set<dat> st;

void dfs(int at, int p) {
    if (p) {
	dat cur({at,p});
	st.insert(cur);
    }
	
    for (int to: g[at]) {
	if (to == p) continue;
	dfs(to, at);
    }
}



int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);  cout.tie(0);

    cin>>n>>m;
    for (int i=1; i<=n; i++) {
	cin>>a[i];
    }

    for (int i=0; i<m; i++) {
	int u,v; cin>>u>>v;
	g[u].push_back(v);
	g[v].push_back(u);
    }


    for (int i=1; i<=n; i++) {
	act[i] = true;
    }
    
    dfs(1, 0);



    map<ll,ll> mp;
    mp[0] = 0; //money->cnt

    ll count = 0;
    ll sum = 0;

    while (st.size()) {
	auto cur = *st.begin();
	st.erase(st.begin());
	if (!cur.active()) {
	    continue;
	}
	sum += cur.sum();
	count += cur.size();
	mp[sum] = count;

	for (int x: cur.inds) {
	    act[x] = false;
	}

	//add neighbors
	for (int x: cur.inds) {
	    for (int y: g[x]) {
		dat cur({y});
		st.insert(cur);
	    }
	}
    }


    cin>>q;

    while (q--) {
	ll x;
	cin>>x;
	auto iter = std::prev(mp.upper_bound(x));
	ll count = iter->second;
	cout<<count<<"\n";
    }
    
    
    return 0;
}

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