Submission #166233

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
166233	2019-12-01T11:38:50 Z	maruii	Designated Cities (JOI19_designated_cities)	C++14	9 / 100	679 ms	49272 KB

designated_cities

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
using ll = long long;
#define ff first
#define ss second

int N, Q, dfn[200005], dfnn, efn[200005], par[200005];
bool used[200005];
vector<pair<int, pii> > edge[200005];
ll ans[200005], D[200005];

ll dfs1(int x, int p) {
	ll ret = 0;
	for (auto i : edge[x]) {
		if (i.ff == p) continue;
		ret += dfs1(i.ff, x) + i.ss.ff;
	}
	return ret;
}

ll dfs2(int x, int p, ll v) {
	ll ret = v;
	for (auto i : edge[x]) {
		if (i.ff == p) continue;
		ll t = v - i.ss.ff + i.ss.ss;
		ret = min(ret, t);
		dfs2(i.ff, x, t);
	}
	return ret;
}

int dfs3(int x, int p) {
	if (x == p) D[x] = 0;
	dfn[x] = ++dfnn;
	par[x] = p;
	int ret = x;
	for (auto i : edge[x]) {
		if (i.ff == p) continue;
		D[i.ff] = D[x] + i.ss.ff;
		int t = dfs3(i.ff, x);
		if (D[ret] < D[t]) ret = t;
	}
	efn[x] = dfnn;
	return ret;
}

const int SIZE = 1 << 18;
struct ST {
	struct Node {
		pair<ll, int> v;
		ll l;
	} A[2 * SIZE];
	void init() {
		for (int i = 1; i <= N; ++i) A[dfn[i] + SIZE].v = {D[i], i};
		for (int i = SIZE - 1; i; --i) A[i].v = max(A[i << 1].v, A[i << 1 | 1].v);
	}
	void busy(int nn) {
		A[nn << 1].v.ff += A[nn].l;
		A[nn << 1].l += A[nn].l;
		A[nn << 1 | 1].v.ff += A[nn].l;
		A[nn << 1 | 1].l += A[nn].l;
		A[nn].l = 0;
	}
	void update(int nn, int ns, int ne, int s, int e, int v) {
		if (ns > e || ne < s) return;
		if (s <= ns && ne <= e) { A[nn].v.ff += v;
			A[nn].l += v;
			return;
		}
		int m = ns + ne >> 1;
		busy(nn);
		update(nn << 1, ns, m, s, e, v);
		update(nn << 1 | 1, m + 1, ne, s, e, v);
		A[nn].v = max(A[nn << 1].v, A[nn << 1 | 1].v);
	}
	pair<ll, int> query(int nn, int ns, int ne, int s, int e) {
		if (ns > e || ne < s) return {0, 0};
		if (s <= ns && ne <= e) return A[nn].v;
		busy(nn);
		int m = ns + ne >> 1;
		return max(query(nn << 1, ns, m, s, e), query(nn << 1 | 1, m + 1, ne, s, e));
	}
	void update(int s, int e, int v) { update(1, 0, SIZE - 1, s, e, v); }
	pair<ll, int> query(int s, int e) { return query(1, 0, SIZE - 1, s, e); }
} seg;

int main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	cin >> N;
	for (int i = 1; i < N; ++i) {
		int a, b, c, d; cin >> a >> b >> c >> d;
		edge[a].emplace_back(b, pii(c, d));
		edge[b].emplace_back(a, pii(d, c));
	}
	ans[0] = dfs2(1, 1, dfs1(1, 1));
	int X = dfs3(1, 1);
	used[X] = 1;
	dfnn = 0;
	dfs3(X, X);
	ans[1] = dfs1(X, X);
	seg.init();

	vector<int> vec;
	for (int i = 2; i <= N; ++i) {
		auto t = seg.query(1, dfnn);
		if (t.ff == 0) {
			while (i <= N) ans[i++] = ans[i - 1];
			break;
		}
		ans[i] = ans[i - 1] - t.ff;
		for (int x = t.ss; !used[x]; x = par[x]) vec.push_back(x);
		while (vec.size()) {
			int a = vec.back(); vec.pop_back();
			used[a] = 1;
			seg.update(dfn[a], efn[a], D[par[a]] - D[a]);
		}
	}

	cin >> Q;
	while (Q--) {
		int x; cin >> x;
		if (x == 1) x--;
		printf("%lld\n", ans[x]);
	}
	return 0;
}

Compilation message

designated_cities.cpp: In member function 'void ST::update(int, int, int, int, int, int)':
designated_cities.cpp:71:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int m = ns + ne >> 1;
           ~~~^~~~
designated_cities.cpp: In member function 'std::pair<long long int, int> ST::query(int, int, int, int, int)':
designated_cities.cpp:81:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int m = ns + ne >> 1;
           ~~~^~~~
designated_cities.cpp: In function 'int main()':
designated_cities.cpp:108:24: warning: operation on 'i' may be undefined [-Wsequence-point]
    while (i <= N) ans[i++] = ans[i - 1];
                       ~^~

Subtask #1
0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	19 ms	17400 KB	Output is correct
2	Incorrect	19 ms	17400 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #2
0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	19 ms	17436 KB	Output is correct
2	Incorrect	631 ms	37812 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #3
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	19 ms	17400 KB	Output is correct
2	Correct	559 ms	37672 KB	Output is correct
3	Correct	638 ms	49272 KB	Output is correct
4	Correct	539 ms	36428 KB	Output is correct
5	Correct	554 ms	37816 KB	Output is correct
6	Correct	594 ms	40104 KB	Output is correct
7	Correct	558 ms	37892 KB	Output is correct
8	Correct	679 ms	45832 KB	Output is correct
9	Correct	497 ms	37856 KB	Output is correct