oj.uz

Submission #424553

# Submission time Handle Problem Language Result Execution time Memory
424553 2021-06-12T05:28:02 Z milleniumEeee Designated Cities (JOI19_designated_cities) C++17
13 / 100
 1066 ms 103040 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;

void dfs(int v, int par, int cur_sum) {
	chmax(mx, cur_sum + (subtask3 ? far[v] : 0));
	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 calc_sub(int v, int par) {
	sub[v] = 0;
	for (auto [to, cost] : g[v]) {
		if (to != par) {
			calc_sub(to, v);
			chmax(sub[v], sub[to] + cost);
		}
	}
}
void calc_far(int v, int par, int up) {
	if (par == -1) { // root
		far[v] = sub[v];
	} else {
		far[v] = sub[v] + up;
	}
	multiset <int> setik;
	for (auto [to, cost] : g[v]) {
		if (to != par) {
			setik.insert(sub[to]);
		}
	}
	for (auto [to, cost] : g[v]) {
		if (to != par) {
			int opt = up;
			setik.erase(setik.find(sub[to]));
			if (!setik.empty()) {
				chmax(opt, *(--setik.end()));
			}
			setik.insert(sub[to]);
			calc_far(to, v, opt + 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];
	}
	calc_t(1, -1);
	if (n <= 16) {
		brute_force();
	}
	else {
		subtask3 = (q == 1 && e[1] == 2);
		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];
		}
		calc_sub(1, -1);
		calc_far(1, -1, 0);
		dfs(1, -1, sum_root);
		cout << sum - mx << endl;
	}
}

Subtask #1
6.0 / 6.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 5068 KB Output is correct
2 Correct 923 ms 55972 KB Output is correct
3 Correct 1057 ms 101860 KB Output is correct
4 Correct 949 ms 56028 KB Output is correct
5 Correct 959 ms 57596 KB Output is correct
6 Correct 950 ms 62624 KB Output is correct
7 Correct 1049 ms 60408 KB Output is correct
8 Correct 1066 ms 103040 KB Output is correct
9 Correct 806 ms 64464 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 5068 KB Output is correct
2 Incorrect 965 ms 56000 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 26 ms 5080 KB Output is correct
3 Correct 27 ms 5068 KB Output is correct
4 Correct 27 ms 5076 KB Output is correct
5 Correct 28 ms 5076 KB Output is correct
6 Correct 28 ms 5068 KB Output is correct
7 Correct 32 ms 5068 KB Output is correct
8 Correct 29 ms 5068 KB Output is correct
9 Correct 28 ms 5076 KB Output is correct
10 Correct 25 ms 5072 KB Output is correct
11 Correct 30 ms 5068 KB Output is correct
12 Correct 10 ms 5068 KB Output is correct
13 Incorrect 8 ms 5588 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 5068 KB Output is correct
2 Correct 923 ms 55972 KB Output is correct
3 Correct 1057 ms 101860 KB Output is correct
4 Correct 949 ms 56028 KB Output is correct
5 Correct 959 ms 57596 KB Output is correct
6 Correct 950 ms 62624 KB Output is correct
7 Correct 1049 ms 60408 KB Output is correct
8 Correct 1066 ms 103040 KB Output is correct
9 Correct 806 ms 64464 KB Output is correct
10 Correct 10 ms 5068 KB Output is correct
11 Incorrect 965 ms 56000 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 26 ms 5080 KB Output is correct
3 Correct 27 ms 5068 KB Output is correct
4 Correct 27 ms 5076 KB Output is correct
5 Correct 28 ms 5076 KB Output is correct
6 Correct 28 ms 5068 KB Output is correct
7 Correct 32 ms 5068 KB Output is correct
8 Correct 29 ms 5068 KB Output is correct
9 Correct 28 ms 5076 KB Output is correct
10 Correct 25 ms 5072 KB Output is correct
11 Correct 30 ms 5068 KB Output is correct
12 Correct 11 ms 5068 KB Output is correct
13 Correct 923 ms 55972 KB Output is correct
14 Correct 1057 ms 101860 KB Output is correct
15 Correct 949 ms 56028 KB Output is correct
16 Correct 959 ms 57596 KB Output is correct
17 Correct 950 ms 62624 KB Output is correct
18 Correct 1049 ms 60408 KB Output is correct
19 Correct 1066 ms 103040 KB Output is correct
20 Correct 806 ms 64464 KB Output is correct
21 Correct 10 ms 5068 KB Output is correct
22 Incorrect 965 ms 56000 KB Output isn't correct
23 Halted 0 ms 0 KB -