Submission #1160730

#	Time	Username	Problem	Language	Result	Execution time	Memory
1160730		antonn	Designated Cities (JOI19_designated_cities)	C++20	23 / 100	2096 ms	42344 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) { // u e lca(x, y)
	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};
}

int sz[N], heavy_son[N], head[N], tin[N], tout[N], timer = 0, id[N];

void build(int u) {
	sz[u] = 1;
	head[u] = u;
	for (auto v : g[u]) {
		build(v);
		sz[u] += sz[v];
		if (sz[v] > sz[heavy_son[u]]) {
			heavy_son[u] = v;
		}
	}
}

void dfs_heavy(int u, int p = 0) {
	tin[u] = ++timer;
	head[u] = p;
	if (heavy_son[u] != 0) {
		dfs_heavy(heavy_son[u], p);
	}
	for (auto v : g[u]) {
		if (v != heavy_son[u]) {
			dfs_heavy(v, v);
		}
	}
	tout[u] = timer;
}

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

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

struct Fenwick {
	int n;
	vector<int> f;
	
	void init(int nn) {
		n = nn;
		f.resize(n + 1);
	}
	
	void add(int i, int x) {
		for (; i <= n; i += i & -i) {
			f[i] += x;
		}
	}
	
	int get(int i) {
		int sum = 0;
		for (; i >= 1; i -= i & -i) {
			sum += f[i];
		}
		return sum;
	}
	
	int get_next(int i) {
		int target = get(i - 1);
		int cnt = 0, sol = 0;
		for (int jump = (1 << 17); jump > 0; jump /= 2) {
			if (sol + jump <= n && cnt + f[sol + jump] <= target) {
				cnt += f[sol + jump];
				sol += jump;
			} 
		}
		return sol + 1;
	}
};

Fenwick f;

void add(int l, int r, ll x) {
	for (int i = l; i <= r; ++i) {
		contrib[i] += x;
	}
}

void mark(int u) {
	int sav = u;
	while (u != 0 && !seen[u]) {
		add(l[u], r[u], -dn[u]);
		dn[u] = 0;
		seen[u] = 1;
		u = par[u];
	}
	vector<pi> intervals;
	u = sav;
	while (u != 0) {
		intervals.push_back({tin[head[u]], tin[u]});
		u = par[head[u]];
	}
	reverse(intervals.begin(), intervals.end());
	
	int i = f.get_next(1);
	int ptr = 0;
	while (i <= n) {
		if (ptr < intervals.size() && intervals[ptr].F <= i && i <= intervals[ptr].S) {
			i = f.get_next(intervals[ptr].S + 1);
			++ptr;
			continue;
		}
		int u = id[i];
		add(l[u], r[u], up[u]);
		totalUP -= up[u];
		if (up[u] != 0) {
			f.add(tin[u], -1);
		}
		up[u] = 0;
		i = f.get_next(i + 1);
	}
}


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);
		}
	}
	
    
	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]);
		}
		build(1);
		dfs_heavy(1, 1);
		for (int i = 1; i <= n; ++i) {
			id[tin[i]] = i;
		}
		
		recalc_contribution(1);
		for (int i = 1; i <= n; ++i) {
			totalUP += up[i];
		}
		for (int u = 1; u <= n; ++u) {
			contrib[l[u]] = sum[DN][u] - sum[UP][u];
		}
		f.init(n);
		for (int i = 1; i <= n; ++i) f.add(i, 1);
		
		for (int z = 1; z <= n; ++z) {
			if (sol[2] == two[z]) {
				mark(who[z].F);
				mark(who[z].S);
				break;
			}
		}
	}
    
	for (int e = 3; e <= n; ++e) {
		sol[e] = sol[e - 1];
		int mx = 1;
		for (int i = 1; i <= n; ++i) {
			if (contrib[l[mx]] < contrib[l[i]]) {
				mx = i;
			}
		}
		sol[e] -= totalUP + contrib[l[mx]];
		mark(mx);
	}
	for (int e = 3; e <= n; ++e) {
		sol[e] = min(sol[e], sol[e - 1]);
	}
    
	int q; cin >> q;
	while (q--) {
		int e;
		cin >> e;
		cout << sol[e] << "\n";
	}
}

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