oj.uz

Submission #424605

# Submission time Handle Problem Language Result Execution time Memory
424605 2021-06-12T07:31:32 Z milleniumEeee Designated Cities (JOI19_designated_cities) C++17
22 / 100
 1642 ms 142888 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;

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

# Verdict Execution time Memory Grader output
1 Correct 13 ms 9676 KB Output is correct
2 Correct 37 ms 9676 KB Output is correct
3 Correct 31 ms 9780 KB Output is correct
4 Correct 30 ms 9756 KB Output is correct
5 Correct 38 ms 9764 KB Output is correct
6 Correct 38 ms 9764 KB Output is correct
7 Correct 34 ms 9676 KB Output is correct
8 Correct 35 ms 9780 KB Output is correct
9 Correct 32 ms 9792 KB Output is correct
10 Correct 30 ms 9676 KB Output is correct
11 Correct 35 ms 9764 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 9772 KB Output is correct
2 Correct 1343 ms 62476 KB Output is correct
3 Correct 1642 ms 125764 KB Output is correct
4 Correct 1314 ms 62220 KB Output is correct
5 Correct 1315 ms 63888 KB Output is correct
6 Correct 1341 ms 72180 KB Output is correct
7 Correct 1408 ms 66592 KB Output is correct
8 Correct 1535 ms 127936 KB Output is correct
9 Correct 1372 ms 70712 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 9676 KB Output is correct
2 Correct 1372 ms 62236 KB Output is correct
3 Correct 1591 ms 142888 KB Output is correct
4 Correct 1358 ms 67172 KB Output is correct
5 Correct 1376 ms 70132 KB Output is correct
6 Correct 1395 ms 80268 KB Output is correct
7 Correct 1448 ms 76224 KB Output is correct
8 Correct 1496 ms 111052 KB Output is correct
9 Correct 1392 ms 76888 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 9676 KB Output is correct
2 Correct 37 ms 9676 KB Output is correct
3 Correct 31 ms 9780 KB Output is correct
4 Correct 30 ms 9756 KB Output is correct
5 Correct 38 ms 9764 KB Output is correct
6 Correct 38 ms 9764 KB Output is correct
7 Correct 34 ms 9676 KB Output is correct
8 Correct 35 ms 9780 KB Output is correct
9 Correct 32 ms 9792 KB Output is correct
10 Correct 30 ms 9676 KB Output is correct
11 Correct 35 ms 9764 KB Output is correct
12 Correct 17 ms 9776 KB Output is correct
13 Incorrect 13 ms 10316 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 9772 KB Output is correct
2 Correct 1343 ms 62476 KB Output is correct
3 Correct 1642 ms 125764 KB Output is correct
4 Correct 1314 ms 62220 KB Output is correct
5 Correct 1315 ms 63888 KB Output is correct
6 Correct 1341 ms 72180 KB Output is correct
7 Correct 1408 ms 66592 KB Output is correct
8 Correct 1535 ms 127936 KB Output is correct
9 Correct 1372 ms 70712 KB Output is correct
10 Correct 12 ms 9676 KB Output is correct
11 Correct 1372 ms 62236 KB Output is correct
12 Correct 1591 ms 142888 KB Output is correct
13 Correct 1358 ms 67172 KB Output is correct
14 Correct 1376 ms 70132 KB Output is correct
15 Correct 1395 ms 80268 KB Output is correct
16 Correct 1448 ms 76224 KB Output is correct
17 Correct 1496 ms 111052 KB Output is correct
18 Correct 1392 ms 76888 KB Output is correct
19 Correct 14 ms 9676 KB Output is correct
20 Incorrect 1358 ms 68724 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 9676 KB Output is correct
2 Correct 37 ms 9676 KB Output is correct
3 Correct 31 ms 9780 KB Output is correct
4 Correct 30 ms 9756 KB Output is correct
5 Correct 38 ms 9764 KB Output is correct
6 Correct 38 ms 9764 KB Output is correct
7 Correct 34 ms 9676 KB Output is correct
8 Correct 35 ms 9780 KB Output is correct
9 Correct 32 ms 9792 KB Output is correct
10 Correct 30 ms 9676 KB Output is correct
11 Correct 35 ms 9764 KB Output is correct
12 Correct 13 ms 9772 KB Output is correct
13 Correct 1343 ms 62476 KB Output is correct
14 Correct 1642 ms 125764 KB Output is correct
15 Correct 1314 ms 62220 KB Output is correct
16 Correct 1315 ms 63888 KB Output is correct
17 Correct 1341 ms 72180 KB Output is correct
18 Correct 1408 ms 66592 KB Output is correct
19 Correct 1535 ms 127936 KB Output is correct
20 Correct 1372 ms 70712 KB Output is correct
21 Correct 12 ms 9676 KB Output is correct
22 Correct 1372 ms 62236 KB Output is correct
23 Correct 1591 ms 142888 KB Output is correct
24 Correct 1358 ms 67172 KB Output is correct
25 Correct 1376 ms 70132 KB Output is correct
26 Correct 1395 ms 80268 KB Output is correct
27 Correct 1448 ms 76224 KB Output is correct
28 Correct 1496 ms 111052 KB Output is correct
29 Correct 1392 ms 76888 KB Output is correct
30 Correct 17 ms 9776 KB Output is correct
31 Incorrect 13 ms 10316 KB Output isn't correct
32 Halted 0 ms 0 KB -