Submission #106541

#	Time	Username	Problem	Language	Result	Execution time	Memory
106541		zbww	Designated Cities (JOI19_designated_cities)	C++14	23 / 100	2056 ms	33976 KiB

designated_cities

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;

typedef long long ll;

const int maxn = 200010;

int mxp[maxn*4], fa[maxn], oval[maxn], dfn[maxn], rdfn[maxn], l[maxn], sz[maxn], vis[maxn], tval[maxn], tag[maxn], mx[maxn], val[maxn], del[maxn], e, n, q;
ll ans[maxn], dis[maxn];
int tot = 0;

int lst[maxn], cnt;

struct Edge {
	int v, w, x;
} E[maxn*2];

struct dat {
	ll mx;
	int mxp;
} tree[maxn*4];

ll add[maxn*4];

inline dat operator+(const dat &x, const dat &y) {
	dat ret;
	if (x.mx < y.mx) {
		ret.mx = y.mx;
		ret.mxp = y.mxp;
	} else {
		ret.mx = x.mx;
		ret.mxp = x.mxp;
	}
	return ret;
}

inline void addEdge(int u, int v, int w) {
	E[e].v = v; E[e].x = l[u]; E[e].w = w; l[u] = e++;
}

void dfs_init(int u, int f) {
	sz[u] = 1; mx[u] = 0;
	lst[++cnt] = u;
	for (int p = l[u]; p >= 0; p = E[p].x) {
		int v = E[p].v;
		if (v != f && !vis[v]) {
			dfs_init(v, u);
			sz[u] += sz[v];
			mx[u] = max(mx[u], sz[v]);
		}
	}
}

inline void pushUp(int rt) {
	tree[rt] = tree[rt<<1] + tree[rt<<1|1];
}

void build(int l, int r, int rt) {
	add[rt] = 0;
	if (l == r) {
		tree[rt].mx = dis[rdfn[l]];
		tree[rt].mxp = l;
		return;
	}
	int m = (l + r) >> 1;
	build(l, m, rt<<1);
	build(m+1, r, rt<<1|1);
	pushUp(rt);
}

inline void modify(const int &rt, const ll &v) {
	tree[rt].mx += v;
	add[rt] += v;
}

inline void pushDown(int rt) {
	if (add[rt]) {
		modify(rt<<1, add[rt]);
		modify(rt<<1|1, add[rt]);
		add[rt] = 0;
	}
}

void update(const int &L, const int &R, const int &v, int l, int r, int rt) {
	if (L <= l && r <= R) {
		modify(rt, v);
		return;
	}
	pushDown(rt);
	int m = (l + r) >> 1;
	if (L <= m) update(L, R, v, l, m, rt<<1);
	if (R > m) update(L, R, v, m+1, r, rt<<1|1);
	pushUp(rt);
}

void dfs_cal(int u, int f, int t) {
	fa[u] = f;
	dfn[u] = ++tot; rdfn[tot] = u;
	sz[u] = 1; tag[u] = t;
	for (int p = l[u]; p >= 0; p = E[p].x) {
		int v = E[p].v;
		if (v != f && !vis[v]) {
			val[v] = E[p].w;
			oval[v] = E[p^1].w;
			dis[v] = dis[u] + val[v];
			dfs_cal(v, u, t);
			sz[u] += sz[v];
		}
	}
} 

ll cur_ans = 0;

void choose(int u) {
	while (u && !del[u]) {
		del[u] = 1;
		update(dfn[u], dfn[u] + sz[u] - 1, -val[u], 1, tot, 1);
		cur_ans += val[u];
		u = fa[u];
	}
}

void calans(int c) {
	int t = tag[rdfn[tree[1].mxp]];
	ll mxv = -1; int mxp = 0;
	for (int i = 1; i <= cnt; i++) {
		int u = lst[i];
		if (u != c && tag[u] != tag[t]) {
			if (dis[u] > mxv) {
				mxv = dis[u];
				mxp = u;
			}
		}
	}
	int u = mxp;
	choose(u);
	for (int i = 2; i <= cnt; i++) {
		choose(rdfn[tree[1].mxp]);
		ans[i] = max(ans[i], cur_ans);
	}
}

namespace DP {
	ll sum[maxn*2];
	void dfs1(int u, int f, int fa_e) {
		if (fa_e != -1) sum[fa_e] = E[fa_e].w;
		for (int p = l[u]; p >= 0; p = E[p].x) {
			int v = E[p].v;
			if (v == f) continue;
			dfs1(v, u, p^1);
			if (fa_e != -1) {
				sum[fa_e] += sum[p^1];
			}
		}
	}
	void dfs2(int u, int f) {
		ll s = 0;
		for (int p = l[u]; p >= 0; p = E[p].x) {
			s += sum[p^1];
		}
		for (int p = l[u]; p >= 0; p = E[p].x) {
			int v = E[p].v;
			if (v == f) continue;
			sum[p] = s - sum[p^1] + E[p].w;
		}
		for (int p = l[u]; p >= 0; p = E[p].x) {
			int v = E[p].v;
			if (v != f) {
				dfs2(v, u);
			}
		}
	}
	void solve() {
		dfs1(1, 0, -1);
		dfs2(1, 0);
	}
}

void solve(int u) {
	cnt = 0;
	dfs_init(u, 0);
	int c = 0, total = cnt;
	for (int i = 1; i <= cnt; i++) {
		int t = lst[i];
		tval[t] = max(total-sz[t], mx[t]);
		if (!c || tval[t] < tval[c]) c = t;
	}
	//处理过 c 的连通块
	dis[c] = 0;
	fa[c] = 0;
	tot = 1;
	dfn[c] = 1; rdfn[1] = c;
	val[c] = oval[c] = 0;
	int scnt = 0;
	for (int p = l[c]; p >= 0; p = E[p].x) {
		int v = E[p].v;
		if (!vis[v]) {
			++ scnt;
			val[v] = E[p].w;
			oval[v] = E[p^1].w;
			dis[v] = val[v];
			fa[v] = c;
			dfs_cal(v, c, v);
		}
	}
	build(1, tot, 1);
	ll sum = 0;
	for (int i = 1; i <= cnt; i++) {
		int t = lst[i];
		sum += oval[t];
		del[t] = 0;
		for (int p = l[t]; p >= 0; p = E[p].x) {
			int v = E[p].v;
			if (vis[v]) sum += DP::sum[p^1];
		}
	}
	ans[1] = max(ans[1], sum);
	if (scnt == 1) {
		if (total == 2) {
			for (int p = l[c]; p >= 0; p = E[p].x) {
				int v = E[p].v;
				if (!vis[v]) {
					sum += val[v];
				}
			}
			ans[2] = max(ans[2], sum);
		}
	} else {
		cur_ans = sum;
		calans(c);
	}
	vis[c] = 1;
	for (int p = l[c]; p >= 0; p = E[p].x) {
		int v = E[p].v;
		if (!vis[v]) {
			solve(v);
		}
	}
}

int main() {
	ll total_sum = 0;
	memset(l, -1, sizeof(l));
	scanf("%d", &n);
	for (int i = 1; i < n; i++) {
		int A, B, C, D;
		scanf("%d%d%d%d", &A, &B, &C, &D);
		addEdge(A, B, C);
		addEdge(B, A, D);
		total_sum += C;
		total_sum += D;
	}
	DP::solve();
	solve(1);
	scanf("%d", &q);
	for (int i = 1; i <= q; i++) {
		int k = 0;
		scanf("%d", &k);
		printf("%lld\n", total_sum-ans[k]);
	}
	return 0;
}

Compilation message (stderr)

designated_cities.cpp: In function 'int main()':
designated_cities.cpp:249:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
designated_cities.cpp:252:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d%d", &A, &B, &C, &D);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
designated_cities.cpp:260:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &q);
  ~~~~~^~~~~~~~~~
designated_cities.cpp:263:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &k);
   ~~~~~^~~~~~~~~~

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