Submission #830695

#	Time	Username	Problem	Language	Result	Execution time	Memory
830695		enerelt14	Two Currencies (JOI23_currencies)	C++14	100 / 100	3250 ms	44916 KiB

currencies

#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <climits>
#include <cmath>
#include <complex>
#include <cstring>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <vector>
using namespace std;

#define ll long long
#define ff first
#define ss second
#define pb push_back

const int MX = 1e5 + 5;
const int mod = 998244353;

int n, m, q;
int a[MX], b[MX];
int p[MX], c[MX];
int s[MX], t[MX], x[MX];
ll y[MX];
int l[MX], r[MX], mid[MX], ans[MX];
int pos[MX], sz[MX], d[MX];
int hld_pa[MX], pa[MX];
ll tree[4 * MX];
int nm[4 * MX];
int cnt, num;
vector<int> adj[MX], h[MX];
vector<pair<int, int>> cst;

void dfs(int u, int pre) {
	pa[u] = pre;
	sz[u] = 1;
	int mx = 0;
	for(int i = 0; i < (int)adj[u].size(); i++) {
		if(adj[u][i] == pre) continue;
		d[adj[u][i]] = d[u] + 1;
		dfs(adj[u][i], u);
		mx = max(mx, sz[adj[u][i]]);
		sz[u] += sz[adj[u][i]];
	}
	for(int i = 0; i < (int)adj[u].size(); i++) {
		if(adj[u][i] == pre) continue;
		if(sz[adj[u][i]] == mx) {
			swap(adj[u][i], adj[u][0]);
			break;
		}
	}
}

void hld(int u) {
	pos[u] = num;
	num++;
	for(int i = 0; i < (int)adj[u].size(); i++) {
		if(d[adj[u][i]] < d[u]) continue;
		if(!i) hld_pa[adj[u][i]] = hld_pa[u];
		else hld_pa[adj[u][i]] = adj[u][i];
	}
	for(int i = 0; i < (int)adj[u].size(); i++) {
		if(d[adj[u][i]] < d[u]) continue;
		hld(adj[u][i]);
	}
}

void update(int id, int l, int r, int pos, int x) {
	tree[id] += x;
	nm[id]++;
	if(l == r) return;
	int mid = (l + r) / 2;
	if(mid < pos) update(id * 2 + 2, mid + 1, r, pos, x);
	else update(id * 2 + 1, l, mid, pos, x);
}

ll query(int id, int l, int r, int L, int R) {
	if(L > r || l > R) return 0;
	if(L <= l && r <= R) return tree[id];
	int mid = (l + r) / 2;
	return query(id * 2 + 1, l, mid, L, R) + query(id * 2 + 2, mid + 1, r, L, R);
}
int ch_p(int id, int l, int r, int L, int R) {
	if(L > r || l > R) return 0;
	if(L <= l && r <= R) return nm[id];
	int mid = (l + r) / 2;
	return ch_p(id * 2 + 1, l, mid, L, R) + ch_p(id * 2 + 2, mid + 1, r, L, R);
}

ll find(int u, int v) {
	if(hld_pa[u] == hld_pa[v]) {
		if(u == v) return 0;
		if(d[u] < d[v]) return query(0, 0, n - 1, pos[u] + 1, pos[v]);
		else return query(0, 0, n - 1, pos[v] + 1, pos[u]);
	}
	if(d[hld_pa[u]] < d[hld_pa[v]]) return find(u, pa[hld_pa[v]]) + query(0, 0, n - 1, pos[hld_pa[v]], pos[v]);
	else return find(pa[hld_pa[u]], v) + query(0, 0, n - 1, pos[hld_pa[u]], pos[u]);
}

bool is;

int cnt_ch_p(int u, int v) {
	if(hld_pa[u] == hld_pa[v]) {
		if(u == v) return 0;
		if(d[u] < d[v]) return ch_p(0, 0, n - 1, pos[u] + 1, pos[v]);
		else return ch_p(0, 0, n - 1, pos[v] + 1, pos[u]);
	}
	if(d[hld_pa[u]] < d[hld_pa[v]]) return cnt_ch_p(u, pa[hld_pa[v]]) + ch_p(0, 0, n - 1, pos[hld_pa[v]], pos[v]);
	else return cnt_ch_p(pa[hld_pa[u]], v) + ch_p(0, 0, n - 1, pos[hld_pa[u]], pos[u]);
}

void go() {
	memset(tree, 0, sizeof(tree));
	for(int i = 0; i < m; i++) {
		update(0, 0, n - 1, pos[cst[i].ss], cst[i].ff);
		for(int j = 0; j < (int)h[i].size(); j++) {
			if(i == 1 && h[i][j] == 0) is = 1;
			ll z = find(s[h[i][j]], t[h[i][j]]);
			if(i == 1 && h[i][j] == 0) is = 0;
			if(z > y[h[i][j]]) {
				if(l[h[i][j]] == r[h[i][j]]) {
					ans[h[i][j]] = i - 1;
					cnt++;
				}
				else {
					r[h[i][j]] = mid[h[i][j]];
					mid[h[i][j]] = (r[h[i][j]] + l[h[i][j]]) / 2;
				}
			}
			else {
				if(l[h[i][j]] == r[h[i][j]]) {
					ans[h[i][j]] = i;
					cnt++;
				}
				else {
					l[h[i][j]] = mid[h[i][j]] + 1;
					mid[h[i][j]] = (r[h[i][j]] + l[h[i][j]]) / 2;
				}
			}
		}
		h[i].clear();
	}
	for(int i = 0; i < q; i++) h[mid[i]].pb(i);
}

void solve() {
	memset(nm, 0, sizeof(nm));
	for(int i = 0; i < m; i++) h[i].clear();
	for(int i = 0; i < q; i++) {
		if(ans[i] >= 0) h[ans[i]].pb(i);
		else ans[i] = 0;
	}
	for(int i = 0; i < m; i++) {
		update(0, 0, n - 1, pos[cst[i].ss], cst[i].ff);
		for(int j = 0; j < (int)h[i].size(); j++) {
			if(h[i][j] == 0) is = 1;
			ans[h[i][j]] = cnt_ch_p(s[h[i][j]], t[h[i][j]]);
			if(h[i][j] == 0) is = 0;
		}
	}
	for(int i = 0; i < q; i++) {
		ans[i] = cnt_ch_p(s[i], t[i]) - ans[i];
		if(ans[i] > x[i]) ans[i] = -1;
		else ans[i] = x[i] - ans[i];
	}
}

int main() {
	ios::sync_with_stdio(0);cin.tie(0);
	cin >> n >> m >> q;
	for(int i = 0; i < n - 1; i++) {
		cin >> a[i] >> b[i];
		a[i]--;
		b[i]--;
		adj[a[i]].pb(b[i]);
		adj[b[i]].pb(a[i]);
	}
	dfs(0, 0);
	hld(0);
	for(int i = 0; i < m; i++) {
		cin >> p[i] >> c[i];
		p[i]--;
		if(d[a[p[i]]] > d[b[p[i]]]) cst.pb({c[i], a[p[i]]});
		else cst.pb({c[i], b[p[i]]});
	}
	sort(cst.begin(), cst.end());
	for(int i = 0; i < q; i++) {
		cin >> s[i] >> t[i] >> x[i] >> y[i];
		s[i]--;
		t[i]--;
		l[i] = 0;
		r[i] = m - 1;
		mid[i] = r[i] / 2;
		h[mid[i]].pb(i);
	}
	while(cnt < q) {
		go();
	}
	solve();
	for(int i = 0; i < q; i++) cout << ans[i] << "\n";
}

• Subtask 1: 10 / 10
• Subtask 2: 28 / 28
• Subtask 3: 30 / 30
• Subtask 4: 32 / 32