Submission #1086111

#	Time	Username	Problem	Language	Result	Execution time	Memory
1086111		ymm	Designated Cities (JOI19_designated_cities)	C++17	7 / 100	383 ms	56784 KiB

designated_cities

#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

const int N = 200'010;
vector<pii> A[N];
int par[N];
ll vup[N], vdown[N], sup[N], sdown[N];
int height[N];
int st[N], ft[N];
int stp[N];
int n;

void dfs(int v, int p, ll vp, int &t, int h)
{
	vup[v] = vdown[v] = sup[v] = sdown[v] = 0;
	height[v] = h;
	par[v] = p;
	for (auto [u, w] : A[v])
		if (u == p)
			vup[v] = w;
	vdown[v] = vp;
	sup[v] = vup[v];
	sdown[v] = vdown[v];
	if (p != -1) {
		sup[v] += sup[p];
		sdown[v] += sdown[p];
	}
	st[v] = t++;
	stp[st[v]] = v;
	for (auto [u, w] : A[v]) {
		if (u == p)
			continue;
		dfs(u, v, w, t, h+1);
	}
	ft[v] = t;
}

struct Seg {
	struct Node {
		ll val;
		ll mx;
	};
	vector<Node> t;
	int sz;

	Seg(int n) {
		t.resize(n*4);
		sz = n;
	}

	void add(int l, int r, ll x, int i, int b, int e) {
		if (l <= b && e <= r) {
			t[i].val += x;
			t[i].mx += x;
			return;
		}
		if (r <= b || e <= l)
			return;
		add(l, r, x, 2*i+1, b, (b+e)/2);
		add(l, r, x, 2*i+2, (b+e)/2, e);
		t[i].mx = max(t[2*i+1].mx, t[2*i+2].mx) + t[i].val;
	}
	void add(int l, int r, ll x) { if (l < r) add(l, r, x, 0, 0, sz); }

	int getmax(int i, int b, int e) {
		if (e-b == 1)
			return b;
		if (t[2*i+1].mx + t[i].val == t[i].mx)
			return getmax(2*i+1, b, (b+e)/2);
		else
			return getmax(2*i+2, (b+e)/2, e);
	}
	pll getmax() { return {getmax(0, 0, sz), t[0].mx}; }

	ll maxval(int l, int r, int i, int b, int e) {
		if (l <= b && e <= r)
			return t[i].mx;
		if (r <= b || e <= l)
			return LONG_LONG_MIN;
		return max(maxval(l, r, 2*i+1, b, (b+e)/2),
		           maxval(l, r, 2*i+2, (b+e)/2, e)) + t[i].val;
	}
	ll maxval(int l, int r) { return (l < r? maxval(l, r, 0, 0, sz): -1e18); }
};

ll greedy_val[N];
int barkh[N];
bool vis[N];
vector<int> greedy_ord;

void first_greedy()
{
	Seg seg(n);
	Loop (i,0,n)
		seg.add(st[i], ft[i], vdown[i]);
	Loop (i,0,n) {
		auto [stv, w] = seg.getmax();
		int v = stp[stv];
		int vs = v;
		greedy_ord.push_back(v);
		greedy_val[v] = w;
		seg.add(st[v], st[v] + 1, -1);
		while (v != -1 && !vis[v]) {
			seg.add(st[v], ft[v], -vdown[v]);
			vis[v] = 1;
			v = par[v];
		}
		barkh[vs] = v;
	}
}

ll ans[N];

void solve1()
{
	ans[1] = 0;
	Loop (i,0,n)
		ans[1] = max(ans[1], sdown[i] - sup[i]);
}

void solve()
{
	int v = greedy_ord[0];
	vector<ll> vallca;
	vector<ll> supv;
	{
		Seg seg(n);
		Loop (i,0,n)
			seg.add(st[i], ft[i], vdown[i]);
		int l = st[v], r = ft[v];
		supv.push_back(sup[v]);
		for (int u = par[v]; u != -1; u = par[u]) {
			ll val = max(seg.maxval(st[u], l), seg.maxval(r, ft[u]));
			val -= sdown[u] + sup[u];
			vallca.push_back(val);
			supv.push_back(sup[u]);
			l = st[u];
			r = ft[u];
		}
		Loop (i,0,vallca.size()-1)
			vallca[i+1] = max(vallca[i], vallca[i+1]);
		reverse(vallca.begin(), vallca.end());
		reverse(supv.begin(), supv.end());
	}
	assert(greedy_val[v] == sdown[v]);
	assert(supv[vallca.size()] == sup[v]);
	ll sum = greedy_val[v];
	Loop (i,1,n) {
		ans[i] = max(ans[i], sum - supv[vallca.size()]);
		int u = greedy_ord[i];
		while ((ll)vallca.size() > height[barkh[u]])
			vallca.pop_back();
		if (vallca.size())
			ans[i+1] = max(ans[i+1], sum + vallca.back());
		sum += greedy_val[u];
	}
	ans[n] = sum;
}

int main()
{
	srand(time(0));
	cin.tie(0) -> sync_with_stdio(false);
	cin >> n;
	Loop (i,1,n) {
		int v, u, c, d;
		cin >> v >> u >> c >> d;
		--v; --u;
		A[v].emplace_back(u, c);
		A[u].emplace_back(v, d);
	}
	int dummy = 0;
	dfs(0, -1, 0, dummy, 0);
	first_greedy();
	solve1();
	solve();
	int q;
	cin >> q;
	ll sumd = 0;
	Loop (i,0,n)
		sumd += vdown[i];
	while (q--) {
		int e;
		cin >> e;
		cout << sumd - ans[e] << '\n';
	}
}

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