Submission #424645

#	Time	Username	Problem	Language	Result	Execution time	Memory
424645		milleniumEeee	Designated Cities (JOI19_designated_cities)	C++17	7 / 100	1397 ms	149352 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
#define int 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;}
 
using namespace std;
 

const int MAXN = (int)2e5 + 5;
const int L = 20;

vector <pii> g[MAXN];
vector <pii> G[MAXN];

int n, q;
int A[MAXN], B[MAXN], C[MAXN], D[MAXN];
int e[MAXN];

int answer[MAXN];

int dist[MAXN];

void calc(int v, int par, int len = 0) {
	dist[v] = len;
	for (auto [to, cost] : G[v]) {
		if (to != par) {
			calc(to, v, len + cost);
		}
	}
}

int tin[MAXN], tout[MAXN];
int tiktak = 0;
int pr[MAXN][L + 1];

void precalc(int v, int par) {
	tin[v] = ++tiktak;
	pr[v][0] = par;
	for (int lv = 1; lv <= L; lv++) {
		pr[v][lv] = pr[pr[v][lv - 1]][lv - 1];
	}
	for (auto [to, cost] : g[v]) {
		if (to != par) {
			precalc(to, v);
		}
	}
	tout[v] = tiktak;
}

bool father(int a, int b) {
	return tin[a] <= tin[b] && tout[b] <= tout[a];
}

int get_lca(int a, int b) {
	if (father(a, b)) {
		return a;
	}
	if (father(b, a)) {
		return b;
	}
	for (int lv = L; lv >= 0; lv--) {
		if (!father(pr[a][lv], b)) {
			a = pr[a][lv];
		}	
	}
	return pr[a][0];
}

void solve(int n, int a, int b) {
	
}

map <pii, int> edge;

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 center[MAXN];

void calc_center(int v, int par, int cur_sum) {
	center[v] = 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;
			calc_center(to, v, cur_sum - cur_cost + cost);
		}
	}
}

signed main() {
	cin >> n;
	for (int i = 1; i < n; i++) {
		cin >> A[i] >> B[i] >> C[i] >> D[i];
		int a = A[i];
		int b = B[i];
		int c = C[i];
		int d = D[i];
		edge[{b, a}] = edge[{a, b}] = i;
		g[a].pb({b, c});
		g[b].pb({a, d});
		G[a].pb({b, c + d});
		G[b].pb({a, c + d});
	}
	cin >> q;
	for (int i = 1; i <= q; i++) {
		cin >> e[i];
	}
	// calc tin tout
	precalc(1, 1);
	if (q == 1 && e[1] == 1) {
		used_id = 1;
		add(1, used_id);
		int sum_root = 0;
		int edge_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];
			}
			edge_sum += C[i] + D[i];
		}
		calc_center(1, -1, sum_root);
		int big = 1;
		for (int i = 1; i <= n; i++) {
			if (center[i] > center[big]) {
				big = i;
			}
		}
		answer[1] = edge_sum - center[big]; 
		cout << answer[1] << endl;
		exit(0);
	} else {
		calc(1, -1);
		int a = 1;
		for (int i = 1; i <= n; i++) {
			if (dist[i] > dist[a]) {
				a = i;
			}
		}
		calc(a, -1);
		int b = 1;
		for (int i = 1; i <= n; i++) {
			if (dist[i] > dist[b]) {
				b = i;
			}
		}
		int edge_sum = 0;
		for (int i = 1; i < n; i++) {
			edge_sum += C[i];
			edge_sum += D[i];
		}
		cout << edge_sum - dist[b];		
	}
}

/*
4
1 4 4 3
4 2 2 7
2 3 1 4
1
1

*/

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