제출 #523391

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
523391		NachoLibre	Designated Cities (JOI19_designated_cities)	C++17	100 / 100	1929 ms	123796 KiB

designated_cities

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
using namespace std;

const int N = 200005;
int n, p5[N];
vector<int> iv[N], v[N];
vector<array<ll, 2> > se[N][2], m5;
map<array<int, 2>, int> e;
array<ll, 2> s[N], spt[N], p1;
array<ll, 3> p2;
ll t0, fp[N], is5[N];
vector<ll> u5, u5c;
bool t5[N];

array<ll, 2> operator+(array<ll, 2> x, int y) {
	x[0] += y;
	return x;
}

void dfs_0(int x = 1, int y = 0) {
	for(int z : iv[x]) {
		if(z == y) continue;
		v[x].push_back(z);
		dfs_0(z, x);
	}
}

void dfs_1(int x = 1) {
	s[x] = {0, x};
	se[x][0].resize(sz(v[x]));
	se[x][1].resize(sz(v[x]));
	for(int z : v[x]) {
		dfs_1(z);
		s[x] = max(s[x], s[z] + e[{x, z}]);
	}
	if(!sz(v[x])) return;
	se[x][0][0] = s[v[x][0]] + e[{x, v[x][0]}];
	for(int i = 1; i < sz(v[x]); ++i) {
		se[x][0][i] = max(se[x][0][i - 1], s[v[x][i]] + e[{x, v[x][i]}]);
	}
	se[x][1].back() = s[v[x].back()] + e[{x, v[x].back()}];
	for(int i = sz(v[x]) - 2; i >= 0; --i) {
		se[x][1][i] = max(se[x][1][i + 1], s[v[x][i]] + e[{x, v[x][i]}]);
	}
}

void dfs_2(int x = 1) {
	for(int i = 0; i < sz(v[x]); ++i) {
		int z = v[x][i];
		array<ll, 2> l = {0, 0}, r = {0, 0};
		if(i > 0) l = se[x][0][i - 1];
		if(i < sz(v[x]) - 1) r = se[x][1][i + 1];
		spt[z] = max(max(l, r), spt[x]) + e[{z, x}];
		dfs_2(z);
	}
}

ll dfs_3(int x = 1) {
	ll y = 0;
	for(int z : v[x]) {
		y += dfs_3(z) + e[{z, x}];
	}
	return y;
}

void dfs_4(ll y, int x = 1) {
	p1 = max(p1, array<ll, 2>{y, x});
	array<ll, 2> t2 = max(s[x], spt[x]);
	array<ll, 3> t3 = {t2[0] + y, t2[1], x};
	p2 = max(p2, t3);
	for(int z : v[x]) {
		dfs_4(y - e[{z, x}] + e[{x, z}], z);
	}
}

void dfs_5(int x = p2[1], int y = 0) {
	p5[x] = y;
	for(int z : iv[x]) {
		if(z == y) continue;
		dfs_5(z, x);
	}
}

void dfs_6(int x = p2[1], int y = 0) {
	if(!t5[x]) {
		is5[x] = is5[y] + e[{y, x}];
	}
	for(int z : iv[x]) {
		if(z == y) continue;
		dfs_6(z, x);
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	#ifdef x
	freopen("x.txt", "r", stdin);
	#endif
	cin >> n;
	for(int i = 1; i < n; ++i) {
		int x, y, c, d;
		cin >> x >> y >> c >> d;
		iv[x].push_back(y);
		iv[y].push_back(x);
		e[{x, y}] = c;
		e[{y, x}] = d;
		t0 += c + d;
	}
	dfs_0();
	dfs_1();
	spt[1] = {0, 1};
	dfs_2();
	dfs_4(dfs_3());
	dfs_5();
	int x = p2[2];
	while(x) {
		t5[x] = 1;
		x = p5[x];
	}
	dfs_6();
	for(int i = 1; i <= n; ++i) {
		m5.push_back(array<ll, 2>{is5[i], i});
	}
	sort(all(m5));
	reverse(all(m5));
	u5 = vector<ll>(n + 1);
	for(auto x : m5) {
		int y = x[1];
		int iy = y;
		while(!t5[y]) {
			u5[iy] += e[{p5[y], y}];
			t5[y] = 1;
			y = p5[y];
		}
	}
	u5c = u5;
	sort(1 + all(u5c));
	fp[1] = t0 - p1[0];
	fp[2] = t0 - p2[0];
	for(int i = n; i >= 3; --i) {
		fp[3 + n - i] = fp[2 + n - i] - u5c[i];
	}
	int q;
	cin >> q;
	for(int i = 0; i < q; ++i) {
		int x;
		cin >> x;
		cout << fp[x] << "\n";
	}
	return 0;
}

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