oj.uz

Submission #424538

# Submission time Handle Problem Language Result Execution time Memory
424538 2021-06-12T05:04:29 Z milleniumEeee Designated Cities (JOI19_designated_cities) C++17
13 / 100
 1088 ms 100312 KB 
#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;
void dfs(int v, int par, int cur_sum) {
	chmax(mx, cur_sum);
	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);
		}
	}
}

//void correct_sol() {
	//int best = INF;
	//for (int i = 1; i <= n; i++) {
		//used_id++;
		//add(i, used_id);
		//best = min(best, calc_ans(used_id));
	//}
	//cout << "best: " << best << endl;
//}

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];
	}
	calc_t(1, -1);
	if (n <= 16) {
		brute_force();
	}
	else {
		used_id = 1;
		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;
	}
}

/*
18
14 15 85 73
5 13 58 66
2 16 85 36
5 1 51 57
10 17 39 91
1 6 78 1
4 8 40 50
1 11 98 44
3 2 57 51
10 14 64 9
15 4 28 56
17 12 55 32
12 11 57 47
15 2 20 83
7 16 8 97
18 8 53 64
7 9 37 34
1
1

*/

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 5068 KB Output is correct
2 Correct 28 ms 5068 KB Output is correct
3 Correct 27 ms 5028 KB Output is correct
4 Correct 28 ms 5076 KB Output is correct
5 Correct 29 ms 5032 KB Output is correct
6 Correct 35 ms 5068 KB Output is correct
7 Correct 27 ms 5068 KB Output is correct
8 Correct 29 ms 5028 KB Output is correct
9 Correct 31 ms 5072 KB Output is correct
10 Correct 26 ms 5072 KB Output is correct
11 Correct 32 ms 5068 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 5068 KB Output is correct
2 Correct 910 ms 53160 KB Output is correct
3 Correct 1040 ms 99236 KB Output is correct
4 Correct 946 ms 53356 KB Output is correct
5 Correct 877 ms 53280 KB Output is correct
6 Correct 969 ms 59804 KB Output is correct
7 Correct 879 ms 53044 KB Output is correct
8 Correct 1088 ms 100312 KB Output is correct
9 Correct 768 ms 52520 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 4940 KB Output is correct
2 Incorrect 826 ms 53256 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 5068 KB Output is correct
2 Correct 28 ms 5068 KB Output is correct
3 Correct 27 ms 5028 KB Output is correct
4 Correct 28 ms 5076 KB Output is correct
5 Correct 29 ms 5032 KB Output is correct
6 Correct 35 ms 5068 KB Output is correct
7 Correct 27 ms 5068 KB Output is correct
8 Correct 29 ms 5028 KB Output is correct
9 Correct 31 ms 5072 KB Output is correct
10 Correct 26 ms 5072 KB Output is correct
11 Correct 32 ms 5068 KB Output is correct
12 Correct 14 ms 5068 KB Output is correct
13 Incorrect 6 ms 5580 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 5068 KB Output is correct
2 Correct 910 ms 53160 KB Output is correct
3 Correct 1040 ms 99236 KB Output is correct
4 Correct 946 ms 53356 KB Output is correct
5 Correct 877 ms 53280 KB Output is correct
6 Correct 969 ms 59804 KB Output is correct
7 Correct 879 ms 53044 KB Output is correct
8 Correct 1088 ms 100312 KB Output is correct
9 Correct 768 ms 52520 KB Output is correct
10 Correct 10 ms 4940 KB Output is correct
11 Incorrect 826 ms 53256 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 5068 KB Output is correct
2 Correct 28 ms 5068 KB Output is correct
3 Correct 27 ms 5028 KB Output is correct
4 Correct 28 ms 5076 KB Output is correct
5 Correct 29 ms 5032 KB Output is correct
6 Correct 35 ms 5068 KB Output is correct
7 Correct 27 ms 5068 KB Output is correct
8 Correct 29 ms 5028 KB Output is correct
9 Correct 31 ms 5072 KB Output is correct
10 Correct 26 ms 5072 KB Output is correct
11 Correct 32 ms 5068 KB Output is correct
12 Correct 14 ms 5068 KB Output is correct
13 Correct 910 ms 53160 KB Output is correct
14 Correct 1040 ms 99236 KB Output is correct
15 Correct 946 ms 53356 KB Output is correct
16 Correct 877 ms 53280 KB Output is correct
17 Correct 969 ms 59804 KB Output is correct
18 Correct 879 ms 53044 KB Output is correct
19 Correct 1088 ms 100312 KB Output is correct
20 Correct 768 ms 52520 KB Output is correct
21 Correct 10 ms 4940 KB Output is correct
22 Incorrect 826 ms 53256 KB Output isn't correct
23 Halted 0 ms 0 KB -