oj.uz

Submission #106516

# Submission time Handle Problem Language Result Execution time Memory
106516 2019-04-19T02:26:14 Z zbww Designated Cities (JOI19_designated_cities) C++14
0 / 100
 2000 ms 40272 KB 
#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;

vector<int> lst;

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

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

ll add[maxn*4];

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.push_back(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]);
		}
	}
}

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);
}

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

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

void update(int L, int R, ll 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);
}

dat ask(int p, int l, int r, int rt) {
	if (l == r) return tree[rt];
	pushDown(rt);
	int m = (l + r) >> 1;
	if (p <= m) return ask(p, l, m, rt<<1);
	else return ask(p, m+1, r, rt<<1|1);
}

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, n, 1);
		cur_ans += val[u];
		u = fa[u];
	}
}

void calans(int c) {
	int t = tag[rdfn[tree[1].mxp]];
	dat T; T.mx = -1; T.mxp = 0;
	for (int i = 0; i < lst.size(); i++) {
		int u = lst[i];
		if (u != c && tag[u] != tag[t]) {
			T = T + ask(dfn[u], 1, n, 1);
		}
	}
	int u = rdfn[T.mxp];
	choose(u);
	for (int i = 2; i <= int(lst.size()); 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) {
			int v = E[p].v;
			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) {
	lst.clear();
	dfs_init(u, 0);
	int c = 0, total = int(lst.size());
	for (int i = 0; i < lst.size(); i++) {
		int t = lst[i];
		tval[t] = max(total-sz[t], mx[t]);
		if (!c || tval[t] < tval[c]) c = t;
	}
	//处理过 c 的连通块
	int mn_p = 0;
	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 = 0; i < lst.size(); 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

designated_cities.cpp: In function 'void calans(int)':
designated_cities.cpp:139:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < lst.size(); i++) {
                  ~~^~~~~~~~~~~~
designated_cities.cpp: In function 'void DP::dfs2(int, int)':
designated_cities.cpp:169:8: warning: unused variable 'v' [-Wunused-variable]
    int v = E[p].v;
        ^
designated_cities.cpp: In function 'void solve(int)':
designated_cities.cpp:194:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < lst.size(); i++) {
                  ~~^~~~~~~~~~~~
designated_cities.cpp:220:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < lst.size(); i++) {
                  ~~^~~~~~~~~~~~
designated_cities.cpp:200:6: warning: unused variable 'mn_p' [-Wunused-variable]
  int mn_p = 0;
      ^~~~
designated_cities.cpp: In function 'int main()':
designated_cities.cpp:256:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
designated_cities.cpp:259: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:267:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &q);
  ~~~~~^~~~~~~~~~
designated_cities.cpp:270:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &k);
   ~~~~~^~~~~~~~~~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1152 KB Output is correct
2 Correct 3 ms 1280 KB Output is correct
3 Correct 3 ms 1152 KB Output is correct
4 Correct 3 ms 1152 KB Output is correct
5 Correct 3 ms 1152 KB Output is correct
6 Correct 3 ms 1152 KB Output is correct
7 Correct 3 ms 1152 KB Output is correct
8 Incorrect 3 ms 1152 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1152 KB Output is correct
2 Execution timed out 2037 ms 40272 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1152 KB Output is correct
2 Execution timed out 2017 ms 40228 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1152 KB Output is correct
2 Correct 3 ms 1280 KB Output is correct
3 Correct 3 ms 1152 KB Output is correct
4 Correct 3 ms 1152 KB Output is correct
5 Correct 3 ms 1152 KB Output is correct
6 Correct 3 ms 1152 KB Output is correct
7 Correct 3 ms 1152 KB Output is correct
8 Incorrect 3 ms 1152 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1152 KB Output is correct
2 Execution timed out 2037 ms 40272 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1152 KB Output is correct
2 Correct 3 ms 1280 KB Output is correct
3 Correct 3 ms 1152 KB Output is correct
4 Correct 3 ms 1152 KB Output is correct
5 Correct 3 ms 1152 KB Output is correct
6 Correct 3 ms 1152 KB Output is correct
7 Correct 3 ms 1152 KB Output is correct
8 Incorrect 3 ms 1152 KB Output isn't correct
9 Halted 0 ms 0 KB -