Submission #410278

#	Time	Username	Problem	Language	Result	Execution time	Memory
410278		amoo_safar	Designated Cities (JOI19_designated_cities)	C++17	9 / 100	640 ms	54888 KiB

designated_cities

// vaziat meshki-ghermeze !
#include <bits/stdc++.h>

#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " : " << x << '\n'

using namespace std;

typedef long long ll;
typedef long double ld;
typedef string str;
typedef pair<ll, ll> pll;

const ll Mod = 1000000007LL;
const int N = 2e5 + 10;
const ll Inf = 2242545357980376863LL;
const ll Log = 30;

set<pll> G[N];
ll ans[N];

set<pll> st;


int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int n;
	cin >> n;
	int u, v, c, d;
	for(int i = 1; i < n; i++){
		cin >> u >> v >> c >> d;
		swap(c, d);
		G[u].insert({v, c});
		G[v].insert({u, d});
	}
	int cnt = 0;
	for(int i = 1; i <= n; i++){
		if((int) G[i].size() == 1){
			cnt ++;
			st.insert({G[i].begin() -> S, i});
			// cerr << "! " << G[i].begin() -> S << ' ' << i << '\n';
		}
	}
	ll sm = 0;
	for(int i = n; i >= 2; i--){
		while(cnt > i){
			pll fr = *st.begin();
			// cerr << "### " << fr.F << ' ' << fr.S << '\n';
			st.erase(fr);
			int adj = G[fr.S].begin() -> F;
			G[fr.S].clear();
			auto it = G[adj].lower_bound(pll(fr.S, -1));
			G[adj].erase(it);
			if(G[adj].size() == 1){

				st.insert({fr.F + G[adj].begin() -> S, adj});
			} else {
				cnt --;
				sm += fr.F;
			}
		}
		ans[i] = sm;
	}
	// cout << '\n';
	int q;
	cin >> q;
	for(int i = 1; i <= q; i++){
		cin >> v;
		assert(v > 1);
		cout << ans[v] << '\n';
	}
	return 0;
}

• Subtask 1: 0 / 6
• Subtask 2: 0 / 7
• Subtask 3: 9 / 9
• Subtask 4: 0 / 17
• Subtask 5: 0 / 17
• Subtask 6: 0 / 44