Submission #1160624

#	Time	Username	Problem	Language	Result	Execution time	Memory
1160624		antonn	Designated Cities (JOI19_designated_cities)	C++20	39 / 100	146 ms	52612 KiB

designated_cities

#include <bits/stdc++.h>

#define F first
#define S second
 
using namespace std;
using ll = long long;
using pi = pair<int, int>;
using vi = vector<int>;
 
template<class T> bool ckmin(T& a, T b) { return b < a ? a = b, true : false; }
template<class T> bool ckmax(T& a, T b) { return a < b ? a = b, true : false; }

const int N = 2e5 + 7;

vector<int> g[N];
int n, dep[N], par[N], up[N], dn[N], l[N], r[N], tt = 0;

void dfs(int u, int p = 0) {
	l[u] = ++tt;
	dep[u] = dep[p] + 1;
	par[u] = p;
	for (auto v : g[u]) {
		if (v != p) {
			dfs(v, u);
		}
	}
	r[u] = tt;
}

const int UP = 0;
const int DN = 1;
ll sum[2][N], sub[2][N], one[N], two[N];

void calc(int u, int p = 0) {
	sum[UP][u] = sum[UP][p] + up[u]; 
	sum[DN][u] = sum[DN][p] + dn[u];
	for (auto v : g[u]) {
		calc(v, u);
		sub[UP][u] += sub[UP][v] + up[v];
		sub[DN][u] += sub[DN][v] + dn[v];
	}
}

pair<ll, int> mx[N];
pi who[N];

void solve2(int u) {
	mx[u] = {sum[DN][u], u};
	for (auto v : g[u]) {
		solve2(v);
		ckmax(mx[u], mx[v]);
	}
	pair<ll, int> mx1 = {0, 0}, mx2 = {0, 0};
	for (auto v : g[u]) {
		if (mx[v] >= mx1) {
			mx2 = mx1;
			mx1 = mx[v];
		} else if (mx[v] >= mx2) {
			mx2 = mx[v];
		}
	}
	two[u] += sub[DN][1] - sub[DN][u] - sum[DN][u];
	two[u] += sum[UP][u];
	two[u] += sub[DN][u] - (mx1.F + mx2.F - 2 * sum[DN][u]);
	who[u] = {mx1.S, mx2.S};
}

bool seen[N];
ll contrib[N], totalUP = 0;

bool is_anc(int u, int v) {
	return l[u] <= l[v] && r[v] <= r[u];
}

void mark(int u) {
	/** il optimizam dupa
	while (u != 0 && !seen[u]) {
		add(l[u], r[u], -dn[u]);
		dn[u] = 0;
		seen[u] = 1;
		u = par[u];
	}
	**/
	for (int i = 1; i <= n; ++i) {
		if (!is_anc(i, u)) {
			totalUP -= up[i];
			up[i] = 0;
		} else {
			dn[i] = 0;
		}
	}
}


void recalc_contribution(int u, int p = 0) {
	sum[UP][u] = sum[UP][p] + up[u]; 
	sum[DN][u] = sum[DN][p] + dn[u];
	for (auto v : g[u]) {
		recalc_contribution(v, u);
	}
}


int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	
	cin >> n;
	vector<array<int, 4>> edges;
	for (int i = 1; i < n; ++i) {
		int a, b, c, d; cin >> a >> b >> c >> d;
		g[a].push_back(b);
		g[b].push_back(a);
		edges.push_back({a, b, c, d});
	}
	dfs(1);
	for (int i = 1; i <= n; ++i) g[i].clear();
    
	for (auto [a, b, c, d] : edges) {
		if (dep[a] > dep[b]) {
			up[a] = c;
			dn[a] = d;
			g[b].push_back(a);
		} else {
			up[b] = d;
			dn[b] = c;
			g[a].push_back(b);
		}
	}
	for (int i = 1; i <= n; ++i) {
		totalUP += up[i];
	}
    
	vector<ll> sol(n + 1, LLONG_MAX);
	calc(1);
	{
		for (int u = 1; u <= n; ++u) {
			one[u] = sub[DN][1] + sum[UP][u] - sum[DN][u];
		}
		for (int u = 1; u <= n; ++u) {
			ckmin(sol[1], one[u]);
		}
	}
	{
		solve2(1);
		for (int z = 1; z <= n; ++z) {
			ckmin(sol[2], two[z]);
		}
		for (int z = 1; z <= n; ++z) {
			if (sol[2] == two[z]) {
				mark(who[z].F);
				mark(who[z].S);
				break;
			}
		}
	}
    
	if (n <= 2000) {
		for (int e = 3; e <= n; ++e) {
			sol[e] = sol[e - 1];
			recalc_contribution(1);
			for (int u = 1; u <= n; ++u) {
				contrib[u] = totalUP + sum[DN][u] - sum[UP][u];
			}
			int mx = 0;
			for (int i = 1; i <= n; ++i) {
				if (contrib[mx] < contrib[i]) {
					mx = i;
				}
			}
			mark(mx);
			sol[e] -= contrib[mx];
		}
	}
    
	int q; cin >> q;
	while (q--) {
		int e;
		cin >> e;
		cout << sol[e] << "\n";
	}
}

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