oj.uz

답안 #424529

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
424529 2021-06-12T04:38:28 Z milleniumEeee Designated Cities (JOI19_designated_cities) C++17
6 / 100
 893 ms 52808 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 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, used_id);
			}
		}
		int bits = __builtin_popcount(mask);
		chmin(ans[bits], calc_ans());
	}
}

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]);
			st.erase(st.find(cost));
			dfs(to, v, cur_sum - cost + *st.begin());
		}
	}
}

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 {
		add(1, 1);
		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;
	}
}

Subtask #1
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 4940 KB Output is correct
2 Correct 28 ms 5068 KB Output is correct
3 Correct 26 ms 5072 KB Output is correct
4 Correct 28 ms 5068 KB Output is correct
5 Correct 27 ms 5072 KB Output is correct
6 Correct 30 ms 5068 KB Output is correct
7 Correct 34 ms 5068 KB Output is correct
8 Correct 28 ms 4992 KB Output is correct
9 Correct 30 ms 5068 KB Output is correct
10 Correct 25 ms 5000 KB Output is correct
11 Correct 31 ms 5068 KB Output is correct

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 5068 KB Output is correct
2 Incorrect 803 ms 52804 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 5064 KB Output is correct
2 Incorrect 893 ms 52808 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 4940 KB Output is correct
2 Correct 28 ms 5068 KB Output is correct
3 Correct 26 ms 5072 KB Output is correct
4 Correct 28 ms 5068 KB Output is correct
5 Correct 27 ms 5072 KB Output is correct
6 Correct 30 ms 5068 KB Output is correct
7 Correct 34 ms 5068 KB Output is correct
8 Correct 28 ms 4992 KB Output is correct
9 Correct 30 ms 5068 KB Output is correct
10 Correct 25 ms 5000 KB Output is correct
11 Correct 31 ms 5068 KB Output is correct
12 Correct 10 ms 5068 KB Output is correct
13 Incorrect 6 ms 5452 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 5068 KB Output is correct
2 Incorrect 803 ms 52804 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 4940 KB Output is correct
2 Correct 28 ms 5068 KB Output is correct
3 Correct 26 ms 5072 KB Output is correct
4 Correct 28 ms 5068 KB Output is correct
5 Correct 27 ms 5072 KB Output is correct
6 Correct 30 ms 5068 KB Output is correct
7 Correct 34 ms 5068 KB Output is correct
8 Correct 28 ms 4992 KB Output is correct
9 Correct 30 ms 5068 KB Output is correct
10 Correct 25 ms 5000 KB Output is correct
11 Correct 31 ms 5068 KB Output is correct
12 Correct 10 ms 5068 KB Output is correct
13 Incorrect 803 ms 52804 KB Output isn't correct
14 Halted 0 ms 0 KB -