Submission #105139

#	Time	Username	Problem	Language	Result	Execution time	Memory
105139		Just_Solve_The_Problem	Designated Cities (JOI19_designated_cities)	C++11	16 / 100	845 ms	66264 KiB

designated_cities

#include <bits/stdc++.h>

#define fr first
#define sc second
#define ll long long

using namespace std;

const int N = (int)2e5 + 7;

int n;

struct T {
	pair <ll, int> tree[N * 4];
	ll add[N * 4];
	T() {
		for (int i = 0; i < N * 4; i++) {
			tree[i] = {0, 0};
		}
		memset(add, 0, sizeof add);
	}
	void push(int v, int l, int r) {
		if (!add[v]) return ;
		if (l != r) {
			add[v + v] += add[v];
			add[v + v + 1] += add[v];
		}
		tree[v].fr += add[v];
		add[v] = 0;
	}
	void upd1(int pos, ll val, int v = 1, int l = 1, int r = n) {
		push(v, l, r);
		if (l == r) {
			tree[v] = {val, l};
			return ;
		}
		int mid = (l + r) >> 1;
		if (pos <= mid) {
			upd1(pos, val, v + v, l, mid);
		} else {
			upd1(pos, val, v + v + 1, mid + 1, r);
		}
		tree[v] = max(tree[v + v], tree[v + v + 1]);
	}
	void upd(int l, int r, ll val, int v = 1, int tl = 1, int tr = n) {
		push(v, tl, tr);
		if (tl > r || tr < l) return ;
		if (l <= tl && tr <= r) {
			add[v] += val;
			push(v, tl, tr);
			return ;
		}
		int mid = (tl + tr) >> 1;
		upd(l, r, val, v + v, tl, mid);
		upd(l, r, val, v + v + 1, mid + 1, tr);
		tree[v] = max(tree[v + v], tree[v + v + 1]);
	}
	pair<ll, int> get(int l, int r, int v = 1, int tl = 1, int tr = n) {
		push(v, tl, tr);
		if (tl > r || tr < l) return {0, 0};
		if (l <= tl && tr <= r) return tree[v];
		int mid = (tl + tr) >> 1;
		return max(get(l, r, v + v, tl, mid), get(l, r, v + v + 1, mid + 1, tr));
	}
};
T tr;

vector<pair<int, int>> gr[N];
ll ans[N];
ll h[N], he[N];
pair <ll, int> dp[N];
int tin[N], tout[N], used[N], par[N], pos[N];
int tiktak;

void precalc(int v, int pr) {
	tin[v] = ++tiktak;
	par[v] = pr;
	for (auto tto : gr[v]) {
		int to = tto.fr;
		int w = tto.sc;
		if (to == pr) {
			continue;
		}
		h[v] += w;
		precalc(to, v);
		h[v] += h[to];
	}
	tout[v] = tiktak;
}

pair < int, int > ans2;

void dfs1(int v, int pr, ll H = 0) {
	ll res = 0;
	for (auto tto : gr[v]) {
		int to = tto.fr;
		int w = tto.sc;
		if (to == pr) {
			H += w;
		}
	}
	ans[1] = min(ans[1], H + h[v]);
	dp[v] = {h[v], v};
	ll mx = 1e18;
	int ind = -1;
	for (auto tto : gr[v]) {
		int to = tto.fr;
		int w = tto.sc;
		if (to == pr) continue;
		dfs1(to, v, H + h[v] - h[to] - w);
		if (mx != 1e18) {
			if (mx + dp[to].fr + h[v] - w - h[to] + H < ans[2]) {
				// cout << mx + dp[to].fr + h[v] - w - h[to] + H << ' ' << dp[ind].sc << ' ' << dp[to].sc << '\n';
				ans[2] = mx + dp[to].fr + h[v] - w - h[to] + H;
				ans2 = {dp[ind].sc, dp[to].sc};
			}
		} 
		if (dp[to].fr - w - h[to] < mx) {
			mx = dp[to].fr - w - h[to];
			ind = to;
		}
		if (dp[to].fr + H + h[v] - h[to] - w < ans[2]) {
			ans[2] = dp[to].fr + H + h[v] - h[to] - w;
			ans2 = {v, dp[to].sc};
		}
		if (make_pair(dp[to].fr + h[v] - w - h[to], dp[to].sc) < dp[v]) {
			dp[v] = make_pair(dp[to].fr + h[v] - w - h[to], dp[to].sc);
		}
	}
}

bool upper(int a, int b) {
	return tin[a] <= tin[b] && tout[a] >= tout[b];
}

void dfs2(int v, int pr, ll H = 0) {
	tin[v] = ++tiktak;
	pos[tin[v]] = v;
	par[v] = pr;
	he[v] = H;
	for (auto tto : gr[v]) {
		int to = tto.fr;
		int w = tto.sc;
		if (to == pr) continue;
		dfs2(to, v, H + (!used[to]) * w);
	}
	tout[v] = tiktak;
}

main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		ans[i] = 1e18;
		dp[i] = {1e18, 0};
	}
	for (int i = 1; i < n; i++) {
		int a, b, c, d;
		scanf("%d %d %d %d", &a, &b, &c, &d);
		gr[a].push_back({b, c});
		gr[b].push_back({a, d});
	}
	precalc(1, 1);
	dfs1(1, 1);
	used[ans2.fr] = 1;
	while (!upper(ans2.fr, ans2.sc)) {
		ans2.fr = par[ans2.fr];
		used[ans2.fr] = 1;
	}
	used[ans2.sc] = 1;
	while (!upper(ans2.sc, ans2.fr)) {
		ans2.sc = par[ans2.sc];
		used[ans2.sc] = 1;
	}
	tiktak = 0;
	dfs2(ans2.fr, ans2.sc);
	for (int i = 1; i <= n; i++) {
		tr.upd1(tin[i], he[i]);
	}
	for (int i = 3; i <= n; i++) {
		ans[i] = ans[i - 1];
		pair<ll, int> asd = tr.get(1, n);
		asd.fr = max(asd.fr, 0LL);
		ans[i] -= asd.fr;
		//cout << i << ' ' << asd.fr << endl;
		int v = pos[asd.sc];
		while (!used[v]) {
			used[v] = 1;
			for (auto tto : gr[v]) {
				int to = tto.fr;
				int w = tto.sc;
				if (used[to] || to == par[v]) continue;
				tr.upd(tin[to], tout[to], -he[v]);
			}
			tr.upd1(tin[v], 0);
			v = par[v];
		}
		// cout << ans[i] << ' ';
	}
	int q;
	scanf("%d", &q);
	while (q--) {
		int x;
		scanf("%d", &x);
		printf("%lld\n", ans[x]);
	}
}

Compilation message (stderr)

designated_cities.cpp: In function 'void dfs1(int, int, long long int)':
designated_cities.cpp:94:5: warning: unused variable 'res' [-Wunused-variable]
  ll res = 0;
     ^~~
designated_cities.cpp: At global scope:
designated_cities.cpp:150:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^
designated_cities.cpp: In function 'int main()':
designated_cities.cpp:190:9: warning: unused variable 'w' [-Wunused-variable]
     int w = tto.sc;
         ^
designated_cities.cpp:151:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
designated_cities.cpp:158: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:200:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &q);
  ~~~~~^~~~~~~~~~
designated_cities.cpp:203:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &x);
   ~~~~~^~~~~~~~~~

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