Submission #424516

#	Time	Username	Problem	Language	Result	Execution time	Memory
424516		milleniumEeee	Designated Cities (JOI19_designated_cities)	C++17	6 / 100	2085 ms	34052 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 tin[MAXN], tout[MAXN];
int tiktak = 0;

void dfs(int v, int par) {
	tin[v] = ++tiktak;
	for (auto [to, cost] : g[v]) {
		if (to != par) {
			dfs(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) {
	for (int i = 1; i < n; i++) {
		int a = A[i];
		int b = B[i];
		if (father(a, b)) {
			if (father(b, x)) {
				//cout << a << " -> " << b << endl;
				used[i][0] = used_id;
			} else {
				//cout << b << " -> " << a << endl;
				used[i][1] = used_id;
			}
		}
		else {
			if (father(a, x)) {
				//cout << b << " -> " << a << endl;
				used[i][1] = used_id;
			}
			else {
				//cout << a << " -> " << b << endl;
				used[i][0] = used_id;
			}
		}
	}
}

int calc_ans() {
	int sum = 0;
	for (int i = 1; i < n; i++) {
		if (used[i][0] != used_id) {
			sum += C[i];
		}
		if (used[i][1] != used_id) {
			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);
			}
		}
		int bits = __builtin_popcount(mask);
		chmin(ans[bits], calc_ans());
	}
}

signed main() {
	//freopen("file.in", "r", stdin);
	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]});
	}
	dfs(1, -1);
	precalc();
	int q;
	cin >> q;
	while (q--) {
		int e;
		cin >> e;
		cout << ans[e] << endl;
	}
}

/*
4
1 2 1 2
1 3 3 4
1 4 5 6
2
1 
2

*/

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