Submission #424605

#	Time	Username	Problem	Language	Result	Execution time	Memory
424605		milleniumEeee	Designated Cities (JOI19_designated_cities)	C++17	22 / 100	1642 ms	142888 KiB

designated_cities

#include <bits/stdc++.h>
#define fr first
#define sc second
#define pii pair<int, int>
#define pb push_back
#define szof(s) (int)s.size()
#define all(s) s.begin(), s.end()
#define fastInp ios_base::sync_with_stdio(0); cin.tie(0);
//#define ll long long

template<class T>void chmax(T &a, T b){if (a < b)a = b;}
template<class T>void chmin(T &a, T b){if (b < a)a = b;}

#define int long long

using namespace std;

const int MAXN  = (int)2e5 + 5;
const int INF = 1e18;

int A[MAXN], B[MAXN], C[MAXN], D[MAXN];
vector <pii> g[MAXN];
int n;
int q;

int tin[MAXN], tout[MAXN];
int tiktak = 0;

void calc_t(int v, int par) {
	tin[v] = ++tiktak;
	for (auto [to, cost] : g[v]) {
		if (to != par) {
			calc_t(to, v);
		}
	}
	tout[v] = tiktak;
}

bool father(int a, int b) {
	return tin[a] <= tin[b] && tout[b] <= tout[a];
}

int used[MAXN][2], used_id = 0;

void add(int x, int color) {
	for (int i = 1; i < n; i++) {
		int a = A[i];
		int b = B[i];
		if (father(a, b)) {
			if (father(b, x)) {
				used[i][0] = color;
			} else {
				used[i][1] = color;
			}
		}
		else {
			if (father(a, x)) {
				used[i][1] = color;
			}
			else {
				used[i][0] = color;
			}
		}
	}
}

int calc_ans(int color) {
	int sum = 0;
	for (int i = 1; i < n; i++) {
		if (used[i][0] != color) {
			sum += C[i];
		}
		if (used[i][1] != color) {
			sum += D[i];
		}
	}
	return sum;
}

int ans[20];

void precalc() {
	fill(ans, ans + 20, INF);
	for (int mask = 1; mask < (1 << 16); mask++) {
		used_id++;
		for (int i = 0; i < 16; i++) {
			if (mask & (1 << i)) {
				add(i + 1, used_id);
			}
		}
		int bits = __builtin_popcount(mask);
		chmin(ans[bits], calc_ans(used_id));
	}
}

int e[MAXN];

void brute_force() {
	precalc();
	for (int i = 1; i <= q; i++) {
		cout << ans[e[i]] << endl;
	}
	exit(0);
}

int mx = 0;
map <pii, int> edge;

int far[MAXN];
int sub[MAXN];

bool subtask3 = false;

vector <int> dist[MAXN];

void f(int v, int par, int len, int root) {
	dist[root].pb(len);
	for (auto [to, cost] : g[v]) {
		if (to == par) {
			continue;
		}
		f(to, v, len + cost, root);
	}
}

void dfs(int v, int par, int cur_sum) {
	int cur_mx = cur_sum + (subtask3 ? far[v] : 0);
	chmax(mx, cur_mx);
	for (auto [to, cost] : g[v]) {
		if (to != par) {
			multiset <int> st;
			int ed = edge[{v, to}];
			st.insert(C[ed]);
			st.insert(D[ed]);
			int cur_cost;
			auto it = st.begin();
			if (*it == cost) {
				it++;
			}
			cur_cost = *it;
			dfs(to, v, cur_sum - cur_cost + cost);
		}
	}
}

int back[MAXN];

void calc_sub_and_back(int v, int par) {
	sub[v] = 0;
	back[v] = 0;
	for (auto [to, cost] : g[v]) {
		if (to != par) {
			calc_sub_and_back(to, v);
			multiset <int> st;
			int ed = edge[{v, to}];
			st.insert(C[ed]);
			st.insert(D[ed]);
			auto it = st.begin();
			if (*it == cost) {
				it++;
			}
			chmax(back[v], back[to] + *it);
			chmax(sub[v], sub[to] + cost);
		}
	}
}

void ers(multiset <int> &st, int x) {
	st.erase(st.find(x));
}

void calc_far(int v, int par, int up) {
	if (par == -1) { // root
		far[v] = sub[v];
	} else {
		far[v] = max(sub[v], up);
	}
	multiset <int> sub_setik;
	for (auto [to, cost] : g[v]) {
		if (to != par) {
			sub_setik.insert(sub[to] + cost);
		}
	}
	for (auto [to, cost] : g[v]) {
		if (to != par) {
			ers(sub_setik, sub[to] + cost);
			int back_cost = -1;
			multiset <int> st;
			int ed = edge[{v, to}];
			st.insert(C[ed]);
			st.insert(D[ed]);
			auto it = st.begin();
			if (*it == cost) {
				it++;
			}
			back_cost = *it;
			int opt = up;
			if (!sub_setik.empty()) {
				chmax(opt, *(--sub_setik.end()));
			}
			sub_setik.insert(sub[to] + cost);
			calc_far(to, v, opt + back_cost);
			
		}
	}
}

signed main() {
	fastInp;
	cin >> n;
	for (int i = 1; i < n; i++) {
		cin >> A[i] >> B[i] >> C[i] >> D[i];
		g[A[i]].pb({B[i], C[i]});
		g[B[i]].pb({A[i], D[i]});
		edge[{A[i], B[i]}] = i;
		edge[{B[i], A[i]}] = i;
	}
	cin >> q;
	for (int i = 1; i <= q; i++) {
		cin >> e[i];
	}
	if (n <= 16) {
		calc_t(1, -1);
		brute_force();
	}
	else {
		calc_t(1, -1);
		calc_sub_and_back(1, -1);
		calc_far(1, -1, 0);
		subtask3 = (q == 1 && e[1] == 2);
		used_id = 1e9;
		add(1, used_id);
		int sum_root = 0;
		int sum = 0;
		for (int i = 1; i < n; i++) {
			if (used[i][0] == used_id) {
				sum_root += C[i];
			}
			if (used[i][1] == used_id) {
				sum_root += D[i];
			}
			sum += C[i] + D[i];
		}
		dfs(1, -1, sum_root);
		cout << sum - mx << endl;
	}
}

/*
anti - case:
19
5 14 3 62
18 10 27 15
15 5 57 88
8 12 67 54
2 12 55 15
16 14 49 7
18 2 7 68
3 7 85 89
11 9 97 90
10 3 98 51
13 2 14 27
5 13 48 40
4 6 14 81
8 17 98 52
15 1 45 98
6 8 76 65
9 3 98 13
14 19 91 99
1
2

*/

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