Submission #1226423

#	Time	Username	Problem	Language	Result	Execution time	Memory
1226423		chaeryeong	Truck Driver (IOI23_deliveries)	C++20	43 / 100	3819 ms	40996 KiB

deliveries

#include "deliveries.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 1;
vector <pair <int, ll>> adj[N];
ll dep[N];
int flag;
pair <ll, ll> e[N];
int nxt[N], sze[N], in[N], revin[N], timer;
#define mid ((l + r) >> 1)
#define tl (node << 1)
#define tr (node << 1 | 1)
struct SegmentTree1 {
	ll tree[N << 2], lazy[N << 2];
	void prop (int l, int r, int node) {
		if (l != r) {
			lazy[tl] += lazy[node];
			lazy[tr] += lazy[node];
		}
		tree[node] += (ll)(r - l + 1) * lazy[node];
		lazy[node] = 0;
	}
	void update (int l, int r, int a, int b, ll c, int node) {
		prop(l, r, node);
		if (l > b || r < a) return;
		if (l >= a && r <= b) {
			lazy[node] += c;
			prop(l, r, node);
			return;
		}
		update(l, mid, a, b, c, tl); 
		update(mid + 1, r, a, b, c, tr);
		tree[node] = tree[tl] + tree[tr];
	}
	ll get (int l, int r, int a, int b, int node) {
		prop(l, r, node);
		if (l > b || r < a) return 0;
		if (l >= a && r <= b) return tree[node];
		return get(l, mid, a, b, tl) + get(mid + 1, r, a, b, tr);
	}
} cur;	
struct SegmentTree2 {
	ll tree[N << 2], sum[N << 2], lazy[N << 2], a[N];
	void init (int l, int r, int node) {
		if (l == r) {
			sum[node] = a[l];
		} else {
			init(l, mid, tl); init(mid + 1, r, tr);
			sum[node] = sum[tl] + sum[tr];
		}
	}
	void prop (int l, int r, int node) {
		if (l != r) {
			lazy[tl] += lazy[node];
			lazy[tr] += lazy[node];
		}
		tree[node] += sum[node] * lazy[node];
		lazy[node] = 0;
	}
	void update (int l, int r, int a, int b, ll c, int node) {
		prop(l, r, node);
		if (l > b || r < a) return;
		if (l >= a && r <= b) {
			lazy[node] += c;
			prop(l, r, node);
			return;
		}
		update(l, mid, a, b, c, tl); update(mid + 1, r, a, b, c, tr);
		tree[node] = tree[tl] + tree[tr];
	}
	ll get (int l, int r, int a, int b, int node) {
		prop(l, r, node);
		if (l > b || r < a) return 0;
		if (l >= a && r <= b) return tree[node];
		return get(l, mid, a, b, tl) + get(mid + 1, r, a, b, tr);
	}
} cur2;	
void dfs (int pos, int par) {
	if (par != -1) {
		for (int i = 0; i < (int)adj[pos].size(); i++) {
			if (adj[pos][i].first == par) {
				adj[pos].erase(adj[pos].begin() + i);
				break;
			}
		}
	}
	sze[pos] = 1;
	for (auto [j, w] : adj[pos]) {
		dfs(j, pos);
		sze[pos] += sze[j];
	}
}
void dfs2 (int pos) {
	in[pos] = timer++; revin[in[pos]] = pos;
	for (auto &j : adj[pos]) {
		if (sze[j.first] > sze[adj[pos][0].first]) {
			swap(adj[pos][0], j);
		}
	}
	for (auto [j, w] : adj[pos]) {
		dep[j] = w + dep[pos];
		nxt[j] = (j == adj[pos][0].first ? nxt[pos] : j);
		e[j] = {w, pos};
		dfs2(j);
	}
}
int n, t[N];
void init (int _N, vector <int> u, vector <int> v, vector <int> w, vector <int> T) {
	flag = 1;
	n = _N;
	for (int i = 0; i < n - 1; i++) {
		flag &= u[i] == i && v[i] == i + 1;
	}
	for (int i = 0; i < n; i++) {
		t[i] = T[i];
	}
	for (int i = 0; i < n - 1; i++) {
		adj[u[i]].push_back({v[i], w[i]});
		adj[v[i]].push_back({u[i], w[i]});
	}
	dfs(0, -1);
	nxt[0] = 0;
	dfs2(0);
	for (int i = 1; i < n; i++) {
		cur2.a[in[i]] = e[i].first;
	}
	cur2.init(0, n - 1, 1);
	for (int i = 0; i < n; i++) {
		int u = i;
		while (nxt[u] != 0) {
			cur.update(0, n - 1, in[nxt[u]], in[u], t[i], 1);
			cur2.update(0, n - 1, in[nxt[u]], in[u], t[i], 1);
			u = e[nxt[u]].second;
		}
		cur.update(0, n - 1, in[0], in[u], t[i], 1);
		cur2.update(0, n - 1, in[0], in[u], t[i], 1);
	}
}
int get_pos (int pos, int par) {
	for (auto [j, w] : adj[pos]) {
		if (j != par) {
			ll o = cur.get(0, n - 1, in[j], in[j], 1);
			ll f = cur.get(0, n - 1, in[0], in[0], 1);
			if (o * 2 > f) {
				return get_pos(j, pos);
			}
		}
	}
	return pos;
}
ll max_time (int s, int x) {
	int delta = x - t[s];
	t[s] = x;
	int u = s;
	while (nxt[u] != 0) {
		cur.update(0, n - 1, in[nxt[u]], in[u], delta, 1);
		cur2.update(0, n - 1, in[nxt[u]], in[u], delta, 1);
		u = e[nxt[u]].second;
	}
	cur.update(0, n - 1, in[0], in[u], delta, 1);
	cur2.update(0, n - 1, in[0], in[u], delta, 1);
	ll sum = 2 * cur2.get(0, n - 1, 0, n - 1, 1);
	int pos = -1; //get_pos(0, -1);
	if (flag) {
		int l = 0, r = n - 1;
		while (l <= r) {
			int m = (l + r) / 2;
			if (cur.get(0, n - 1, m, m, 1) * 2 > cur.get(0, n - 1, 0, 0, 1)) {
				pos = revin[m];
				l = m + 1;
			} else {
				r = m - 1;
			}
		}
		assert(pos != -1);
	} else {
		pos = get_pos(0, -1);
	}

	sum += 2 * dep[pos] * (1 + cur.get(0, n - 1, in[0], in[0], 1));
	while (nxt[pos] != 0) {
		sum -= 4 * cur2.get(0, n - 1, in[nxt[pos]], in[pos], 1);
		pos = e[nxt[pos]].second;
	}
	sum -= 4 * (cur2.get(0, n - 1, in[0], in[pos], 1) - cur2.get(0, n - 1, in[0], in[0], 1));
	return sum;
}

• Subtask 1: 8 / 8
• Subtask 2: 21 / 21
• Subtask 3: 14 / 14
• Subtask 4: 0 / 21
• Subtask 5: 0 / 36