Submission #204081

#	Time	Username	Problem	Language	Result	Execution time	Memory
204081		ics0503	Designated Cities (JOI19_designated_cities)	C++17	100 / 100	865 ms	94968 KiB

designated_cities

#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
struct xy { long long x, y, z; };
vector<xy>edge[212121];
long long D[212121], F[212121], FW[212121];
void get_DF(long long w,long long bef) {
	D[w] = F[w] = 0; FW[w] = w;
	for (xy E : edge[w]) if (E.x != bef) {
		get_DF(E.x, w);
		D[w] += D[E.x] + E.y;
		if (F[w] < F[E.x] + E.z) {
			F[w] = F[E.x] + E.z;
			FW[w] = FW[E.x];
		}
	}
}
long long resX[212121], resY[212121], l[212121], r[212121];
void get_res(long long w, long long bef, long long fromRoot) {
	long long sum = 0, cnt = 0;
	vector<pair<long long, long long>>L;
	for (xy E : edge[w]) if (E.x != bef) {
		sum += D[E.x] + E.y;
		L.push_back({ -(F[E.x] + E.z), FW[E.x] });
	}
	sort(L.begin(), L.end());
	resX[w] = sum + fromRoot;
	if (L.size() > 0)resY[w] = -(L[0].first) + sum + fromRoot, l[w] = w, r[w] = L[0].second;
	if (L.size() > 1)resY[w] = -(L[0].first + L[1].first) + sum + fromRoot, l[w] = L[0].second, r[w] = L[1].second;
	for (xy E : edge[w]) if (E.x != bef) get_res(E.x, w, fromRoot + sum - (D[E.x] + E.y) + E.z);
}
//segtree
struct ND { long long l, r; long long max, maxw, pls; }tree[616161]; long long treen = 1;
void update(long long w) {
	long long l = tree[w].l, r = tree[w].r;
	if (tree[l].max >= tree[r].max) tree[w].max = tree[l].max, tree[w].maxw = tree[l].maxw;
	else tree[w].max = tree[r].max, tree[w].maxw = tree[r].maxw;
}
void spread(long long w) {
	long long l = tree[w].l, r = tree[w].r, pls = tree[w].pls;
	tree[l].max += pls; tree[l].pls += pls;
	tree[r].max += pls; tree[r].pls += pls;
	tree[w].pls = 0;
}
void plsV(long long now, long long s, long long e, long long l, long long r, long long v) {
	if (s != e)spread(now);
	if (s == l&&e == r) {
		tree[now].pls += v;
		tree[now].max += v;
		if (l == r)tree[now].maxw = l;
		return;
	}
	if (tree[now].l == 0) { tree[now].l = ++treen; tree[treen] = { 0, 0, 0, 0 }; }
	if (tree[now].r == 0) { tree[now].r = ++treen; tree[treen] = { 0, 0, 0, 0 }; }
	long long m = (s + e) / 2;
	if (l <= m)plsV(tree[now].l, s, m, l, min(r, m), v);
	if (m + 1 <= r)plsV(tree[now].r, m + 1, e, max(l, m + 1), r, v);
	update(now);
}
long long getMinV() {
	if (tree[1].max == 0)return -1;
	return tree[1].maxw;
}

long long S[212121], E[212121], R[212121], dfscnt = 0, pr[212121]; long long prV[212121], depth[212121], n;
void dfs(long long w, long long bef, long long befV, long long dep) {
	S[w] = ++dfscnt;  pr[w] = bef; prV[w] = befV; depth[w] = dep;
	R[S[w]] = w;
	for (xy E : edge[w]) if (E.x != bef) {
		dfs(E.x, w, E.z, dep + E.z);
	}
	E[w] = dfscnt;
}
long long eraseE(long long w) {
	if (prV[w] == 0)return 0;
	plsV(1, 1, n, S[w], E[w], -prV[w]);
	long long res = prV[w];
	prV[w] = 0;
	res+=eraseE(pr[w]);
	return res;
}
long long ans[212121];
int main() {
	long long  i, j, allsum = 0; scanf("%lld", &n);
	for (i = 0; i < n - 1; i++) {
		long long s, e, a, b; scanf("%lld%lld%lld%lld", &s, &e, &a, &b);
		allsum += a; allsum += b;
		edge[s].push_back({ e, b, a });
		edge[e].push_back({ s, a, b });
	}
	get_DF(1, -1);
	get_res(1, -1, 0);
	long long rootSum = 0, root = 1;
	for (i = 1; i <= n; i++) if (ans[1] < resX[i])ans[1] = resX[i];
	for (i = 1; i <= n; i++) if (rootSum < resY[i])rootSum = resY[i], root = i;
	ans[1] = allsum - ans[1];
	ans[2] = allsum - rootSum;
	dfs(root, -1, 0, 0);
	for (i = 1; i <= n; i++) {
		plsV(1, 1, n, S[i], S[i], depth[i]);
	}
	eraseE(l[root]);
	eraseE(r[root]);
	for (i = 3; i <= n; i++) {
		long long v = R[getMinV()];
		if (v == -1) { ans[i] = ans[i - 1]; continue; }
		ans[i] = ans[i-1] - eraseE(v);
	}
	long long q, x; scanf("%lld", &q);
	for (i = 0; i < q; i++) {
		scanf("%lld", &x);
		printf("%lld\n", ans[x]);
	}
	return 0;
}  

Compilation message (stderr)

designated_cities.cpp: In function 'void get_res(long long int, long long int, long long int)':
designated_cities.cpp:21:21: warning: unused variable 'cnt' [-Wunused-variable]
  long long sum = 0, cnt = 0;
                     ^~~
designated_cities.cpp: In function 'int main()':
designated_cities.cpp:85:16: warning: unused variable 'j' [-Wunused-variable]
  long long  i, j, allsum = 0; scanf("%lld", &n);
                ^
designated_cities.cpp:85:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  long long  i, j, allsum = 0; scanf("%lld", &n);
                               ~~~~~^~~~~~~~~~~~
designated_cities.cpp:87:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   long long s, e, a, b; scanf("%lld%lld%lld%lld", &s, &e, &a, &b);
                         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
designated_cities.cpp:110:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  long long q, x; scanf("%lld", &q);
                  ~~~~~^~~~~~~~~~~~
designated_cities.cpp:112:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", &x);
   ~~~~~^~~~~~~~~~~~

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