제출 #1315135

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1315135		vlomaczk	Designated Cities (JOI19_designated_cities)	C++20	0 / 100	2093 ms	86764 KiB

designated_cities

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
typedef long long ll;
using namespace __gnu_pbds;
using namespace std;

template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

ll M = 200'010;
vector<ll> ans(M, 0), only(M), depth(M), sajz(M), par(M), is_off(M), cost(M), pre(M), post(M);
vector<vector<pair<ll, ll>>> g(M);
ll added = 0,nxt;

struct SegTree {
	ll base=1;
	vector<pair<ll,ll>> T;
	vector<ll> L;

	void push(ll v, ll l, ll r) {
		if(L[v]==0 || v >= base) return;
		T[l].first += L[v];
		T[r].first += L[v];
		L[l] += L[v];
		L[r] += L[v];
		L[v] = 0;
	}

	void ustaw(ll x, ll val) {
		x+=base;
		T[x] = {0,val};
		x/=2;
		while(x>0) {
			T[x] = max(T[x+x],T[x+x+1]);
			x/=2;
		}
	}

	void update(ll v, ll a, ll b, ll p, ll k, ll val) {
		if(b < p || k < a) return;
		if(p<=a && b<=k) {
			T[v].first += val;
			L[v] += val;
			return;
		}
		ll l=2*v; ll r=2*v+1; ll mid=(a+b)/2;
		push(v,l,r);
		update(l,a,mid,p,k,val);
		update(r,mid+1,b,p,k,val);
		T[v] = max(T[l], T[r]);
	}

	pair<ll,ll> query(ll v, ll a, ll b, ll p, ll k) {
		if(b < p || k < a) return {-1,0};
		if(p<=a && b<=k) {
			return T[v];
		}
		ll l=2*v; ll r=2*v+1; ll mid=(a+b)/2;
		push(v,l,r);
		return max(query(l,a,mid,p,k), query(r,mid+1,b,p,k));
	}

	void init(ll n) {
        base = 1;
        while (base < n) base *= 2;
        T.assign(2 * base, {0, 0});
        L.assign(2 * base, 0);
    }
};

void only_dfs(ll v, ll p) {
	depth[v] = depth[p] + 1;
	for(auto[u,k] : g[v]) {
		if(u==p) continue;
		only[u] += only[v];
		only_dfs(u,v);
	}
}

void sajz_dfs(ll v, ll p) {
	sajz[v] = 1;
	par[v] = p;
	for(auto[u,k] : g[v]) {
		if(u==p || is_off[u]) continue;
		sajz_dfs(u,v);
		sajz[v] += sajz[u];
	}
}

ll n;
SegTree st;
vector<int> V;

void pre_dfs(ll v, ll p) {
	for(auto[u,k] : g[v]) if(u==p) cost[v] = k;
	pre[v] = ++nxt;
	st.ustaw(pre[v], v);
	for(auto[u,k] : g[v]) {
		if(u==p || is_off[u]) continue;
		pre_dfs(u,v);
	}
	post[v] = ++nxt;
	st.ustaw(post[v],v);
	V.push_back(v);
}

void centroid_decomposition(ll v) {
	st.init(3*n+100);
	pre.assign(M,0); post.assign(M,0);
	while(V.size()) V.pop_back();
	sajz_dfs(v,v);
	if(g[v].size() < 2) return;
	nxt=1;
	cost[v] = 0;
	pre_dfs(v,v);
	ll cnt = 0;
	ll res = only[v];
	for(auto x : V) st.update(1,0,st.base-1,pre[x],post[x],cost[x]);
	vector<pair<ll,ll>> F;
	for(auto[u,k] : g[v]) {
		F.push_back(st.query(1,0,st.base-1,pre[u],post[u]));
	}
	sort(F.begin(), F.end());
	reverse(F.begin(), F.end());
	auto obsluz = [&](pair<ll, ll> para) {
		cnt++;
		ll x = para.second;
		res += para.first;
		while(cost[x] > 0) {
			st.update(1,0,st.base-1,pre[x],post[x],-cost[x]);
			cost[x]=0;
			x=par[x];
		}
		if(cnt > 1) ans[cnt] = max(ans[cnt], res);
	};
	if(F.size()>=1) obsluz(F[0]);
	if(F.size()>=2) obsluz(F[1]);
	while(st.T[1].first > 0) {
		obsluz(st.T[1]);
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	cin >> n;
	ll sum = 0;
	vector<pair<pair<ll, ll>, pair<ll, ll>>> edges;
	for(ll i=1; i<n; ++i) {
		ll a,b,c,d;
		cin >> a >> b >> c >> d;
		swap(c,d);
		g[a].push_back({b,c});
		g[b].push_back({a,d});
		edges.push_back({{a,c},{b,d}});
		sum += c + d;		
	}
	only_dfs(1,0);
	for(auto[x,y] : edges) {
		if(depth[y.first] > depth[x.first]) swap(x,y);
		auto[a,c] = x;
		auto[b,d] = y;
		only[a] += c-d;
		added += d;
	}
	only_dfs(1,0);
	for(auto[x,y] : edges) {
		auto[a,c] = x;
		auto[b,d] = y;
		ans[2] = max(ans[2], only[a] + d);
	}
	for(ll i=1; i<=n; ++i) {
		only[i] += added;
		ans[1] = max(ans[1], only[i]);
	}
	for(int i=1; i<=n; ++i) {
		centroid_decomposition(i);
	}
	// centroid_decomposition(1);
	ll q; cin >> q;
	while(q--) {
		ll x; cin >> x;
		cout << sum - ans[x] << "\n";
	}

	return 0;
}

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