Submission #629603

#	Time	Username	Problem	Language	Result	Execution time	Memory
629603		Arnch	Designated Cities (JOI19_designated_cities)	C++17	7 / 100	446 ms	118244 KiB

designated_cities

// oooo
/*
 har chi delet mikhad bebar ~
 gitar o ba khodet nabar! ~
 ;Amoo_Hasan;
*/

#include<bits/stdc++.h>
//#pragma GCC optimize("O3,no-stack-protector,unroll-loops")
//#pragma GCC target("avx2,fma")

using namespace std;

typedef long long ll;
typedef long double ld;

#define Sz(x) int((x).size())
#define All(x) (x).begin(), (x).end()
#define wtf(x) cout<<#x <<" : " <<x <<endl
#define mak make_pair

//constexpr int PRI = 1000696969;
constexpr ll INF = 1e18, N = 1e6 + 10, MOD = 1e9 + 7, LOG = 30;

ll root, sum, total;
ll jad[N], cnt[N];
int par[N][LOG], h[N];
ll ans[N], ps[N], sf[N];
vector<pair<ll, ll> > vc[N];
vector<pair<int, int> > adj[N];

bool cmp(int i, int j) {
	return cnt[i] > cnt[j];
}

void pre_dfs(int x, int p = 0) {
	par[x][0] = p;
	for(int i = 1; i < LOG; i++) par[x][i] = par[par[x][i - 1]][i - 1];
	h[x] = h[p] + 1;
	ps[x] = ps[p];

	for(auto j : adj[x]) {
		if(j.first == p) {
			sum += j.second;
			ps[x] += j.second;
		}
	}
	for(auto j : adj[x]) {
		if(j.first == p) {
			continue;
		}
		sf[j.first] = sf[x] + j.second;
		pre_dfs(j.first, x);
	}
}
int get_par(int x, int y) {
	for(int i = 0; i < LOG; i++)
		if((y >> i) & 1)
			x = par[x][i];
	return x;
}
int lca(int x, int y) {
	if(h[x] > h[y]) swap(x, y);
	y = get_par(y, h[y] - h[x]);
	if(x == y) return x;
	for(int i = LOG - 1; i >= 0; i--) 
		if(par[x][i] != par[y][i])
			x = par[x][i], y = par[y][i];
	return par[x][0];
}	

void dfs(int x, int p = 0) {
	if(Sz(adj[x]) == 1) vc[x].push_back({0, x});
	for(auto j : adj[x]) {
		if(j.first == p) continue;
		dfs(j.first, x);
		pair<ll, ll> p = vc[j.first][0];
		vc[x].push_back(mak(p.first + j.second, p.second));
	}
	sort(All(vc[x]), greater<pair<ll, ll> >());
	
	while(Sz(vc[x]) > 1) {
		pair<ll, ll> p = vc[x].back(); 
		vc[x].pop_back();

		jad[p.second] = x;
		cnt[p.second] = p.first;
	}

	if(x == root && Sz(vc[x]) > 0) {
		pair<ll, ll> p = vc[x].back();
		vc[x].pop_back();

		jad[p.second] = x;
		cnt[p.second] = p.first;
	}
}

int main() {
	ios :: sync_with_stdio(0), cin.tie(0); cout.tie(0);
	
	int n; cin >>n;
	for(int i = 0; i < n - 1; i++) {
		int u, v, a, b; cin >>u >>v >>a >>b;
		adj[u].push_back({v, a});
		adj[v].push_back({u, b});

		total += a + b;
	}

	if(n == 2) {
		int q; cin >>q;
		for(int j = 0; j < q; j++) {
			int e; cin >>e;
			if(e == 2) cout<<total <<endl;
			else {
				cout<<total - max(adj[1][0].second, adj[2][0].second) <<endl;
			}
		}
		return 0;
	}

	for(int i = 1; i <= n; i++) {
		if(Sz(adj[i]) > 1) {
			root = i;
			break;
		}
	}
	pre_dfs(root);
	dfs(root);

	vector<int> leaf;
	for(int i = 1; i <= n; i++) {
		if(Sz(adj[i]) == 1) leaf.push_back(i);
	}	
	sort(All(leaf), cmp);

	ll last = 0, val = 0;
	for(int i = 0; i < Sz(leaf); i++) {
		if(i == 0) last = leaf[i];
		else last = lca(last, leaf[i]);
	
		val += cnt[leaf[i]];

		ans[i + 1] = total - (val - ps[last] + sum);

//		cout<<"^^" <<i <<' ' <<leaf[i] <<' ' <<val <<' ' <<ps[last] <<' ' <<sum <<' ' <<ans[i] <<endl;
	}

	val = 0;
	for(int i = 1; i <= n; i++) {
		val = max(val, sum + sf[i] - ps[i]);
//		cout<<"^^" <<i <<' ' <<sf[i] <<' ' <<ps[i] <<endl;
	}

	int q; cin >>q;
	for(int i = 0; i < q; i++) {
		int e; cin >>e;

		if(e == 1) {
			cout<<total - val <<endl;
			continue;
		}

		cout<<ans[min(Sz(leaf), e)] <<endl;
	}

	return 0;
}

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