Submission #1226432

#	Time	Username	Problem	Language	Result	Execution time	Memory
1226432		chaeryeong	Truck Driver (IOI23_deliveries)	C++20	100 / 100	2682 ms	45112 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];
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 SegmentTree3 {
	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] += 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] = max(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 max(get(l, mid, a, b, tl), get(mid + 1, r, a, b, tr));
	}
	int dfs (int l, int r, ll x, int node) {
		prop(l, r, node);
		if (tree[node] * 2 <= x) {
			return -1;
		}
		if (l == r) {
			return l;
		}
		int u = dfs(mid + 1, r, x, tr);
		if (u != -1) {
			return u;
		}
		return dfs(l, mid, x, tl);
	}
} cur3;	
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) {
	n = _N;
	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);
			cur3.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);
		cur3.update(0, n - 1, in[0], in[u], t[i], 1);
	}
}

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);
		cur3.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);
	cur3.update(0, n - 1, in[0], in[u], delta, 1);

	int pos = 0; //get_pos(0, -1);
	pos = cur3.dfs(0, n - 1, cur.get(0, n - 1, 0, 0, 1), 1);
	pos = revin[pos];

	ll sum = 2 * cur2.get(0, n - 1, 0, n - 1, 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: 21 / 21
• Subtask 5: 36 / 36