Submission #410278

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
410278	2021-05-22T12:12:21 Z	amoo_safar	Designated Cities (JOI19_designated_cities)	C++17	9 / 100	640 ms	54888 KB

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.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	14 ms	19532 KB	Execution killed with signal 6
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	14 ms	19424 KB	Execution killed with signal 6
2	Halted	0 ms	0 KB	-

Subtask #3
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	9676 KB	Output is correct
2	Correct	417 ms	47768 KB	Output is correct
3	Correct	243 ms	42584 KB	Output is correct
4	Correct	356 ms	46448 KB	Output is correct
5	Correct	464 ms	48484 KB	Output is correct
6	Correct	401 ms	47840 KB	Output is correct
7	Correct	623 ms	54116 KB	Output is correct
8	Correct	312 ms	46256 KB	Output is correct
9	Correct	640 ms	54888 KB	Output is correct