제출 #1308105

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1308105		minh30082008	Two Currencies (JOI23_currencies)	C++20	100 / 100	438 ms	133780 KiB

currencies

#include<bits/stdc++.h>
#define INF 1e18
#define fi first
#define se second
#define FOR(i, k, n) for(ll i = k; i <= n; i++)
#define FOR1(i, k, n) for(ll i = k; i >= n; i--)
#define pb push_back
#define fastio ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define vi vector<int>
#define pii pair<int, int>
#define vii vector<pii>
#define ll long long
#define vll vector<ll>
#define pll pair<ll, ll>
#define re return 0
#define mii map<int, int>
#define input "CANDY.inp"
#define output "CANDY.out"
#define rf 	freopen(input, "r", stdin); freopen(output, "w", stdout)
#define int ll
using namespace std;
const int maxn = 1e5 + 5;
const int mod = 1e9 + 7;
const int base = 998244353;
void add(int &a, int b) 
{
	a += b; 
	if(a >= mod) a -= mod; 
	if(a < 0) a += mod; 
}
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
int rand(int l, int r)
{
	return uniform_int_distribution<int>(l, r) (rd);
}
int n, m, q;
int depth[maxn], version[maxn], cntnode, cnt[20][maxn], par[20][maxn];
vi query[maxn], adj[maxn], vv;
struct shape{
	int cnt, l, r;
	ll sum;
	shape(){
		l = r = cnt = sum = 0;
	}
} T[maxn * 25];
int build(int l, int r)
{
	int node = ++cntnode;
	if(l == r)
	{
		return node;
	}
	int mid = (l + r) >> 1;
	T[node].l = build(l, mid);
	T[node].r = build(mid + 1, r);
	return node;
}
void DFS(int u, int p)
{
	for(auto v : adj[u])
	{
		if(v == p)
			continue;
		depth[v] = depth[u] + 1;
		DFS(v, u);
	}
}
int update(int l, int r, int pos, int old)
{
	int node = ++cntnode;
	T[node] = T[old];
	if(l == r)
	{
		T[node].cnt++;
		T[node].sum += vv[l];
		return node;
	}
	int mid = (l + r) >> 1;
	if(pos <= mid)
		T[node].l = update(l, mid, pos, T[old].l);
	else
		T[node].r = update(mid + 1, r, pos, T[old].r);
	T[node].cnt = T[T[node].l].cnt + T[T[node].r].cnt;
	T[node].sum = T[T[node].l].sum + T[T[node].r].sum;
	return node;
}
void DFS1(int u)
{
	for(auto v : adj[u])
	{
		if(v == par[0][u])
			continue;
		par[0][v] = u;
		FOR(i, 1, 18)
		{
			par[i][v] = par[i - 1][par[i - 1][v]];
			cnt[i][v] = cnt[i - 1][v] + cnt[i - 1][par[i - 1][v]];
		}
		if(query[v].empty())
			version[v] = version[u];
		else
		{
			int id = lower_bound(vv.begin(), vv.end(), query[v][0]) - vv.begin();
			version[v] = update(1, vv.size(), id, version[u]);
			FOR(i, 1, query[v].size() - 1)
			{
				id = lower_bound(vv.begin(), vv.end(), query[v][i]) - vv.begin();
				version[v] = update(1, vv.size(), id, version[v]);
			}
		}
		DFS1(v);
	}
}
pii LCA(int u, int v)
{
	if(depth[u] < depth[v])
		swap(u, v);
	int h = depth[u] - depth[v];
	int dem = 0;
	FOR1(i, 18, 0)
		if(h >= (1 << i))
		{
			dem += cnt[i][u];
			u = par[i][u];
			h -= (1 << i);
		}
	if(u == v)
		return {u,  dem};
	FOR1(i, 18, 0)
		if(par[i][v] != par[i][u])
		{
			dem += cnt[i][v];
			dem += cnt[i][u];
			u = par[i][u];
			v = par[i][v];
		}
	dem += cnt[0][u] + cnt[0][v];
	return {par[0][u], dem};
}
pll tinh(int x, int y, int z)
{
	int dem = 0;
	ll sum = 0;
	dem = T[x].cnt + T[y].cnt - 2 * T[z].cnt;
	sum = T[x].sum + T[y].sum - 2 * T[z].sum;
	return {dem, sum};
}
int get(int l, int r, int u, int v, int lca, ll val)
{
	pll tmp = tinh(u, v, lca);
	if(tmp.se <= val)
		return tmp.fi;
	if(l == r)
	{
		pll tmp = tinh(u, v, lca);
		int dem = tmp.fi;
		return min((ll)dem, val / vv[l]);
	}
	int mid = (l + r) >> 1;
	tmp = tinh(T[u].l, T[v].l, T[lca].l);
	if(tmp.se <= val)
	{
		return tmp.fi + get(mid + 1, r, T[u].r, T[v].r, T[lca].r, val - tmp.se);
	}
	return get(l, mid, T[u].l, T[v].l, T[lca].l, val);
}
signed main()
{
	fastio;
	vii adj1;
	cin >> n >> m >> q;
	FOR(i, 1, n - 1)
	{
		int u, v;
		cin >> u >> v;
		adj[u].pb(v);
		adj[v].pb(u);
		adj1.pb({u, v});
	}
	DFS(1, 0);
	FOR(i, 1, m)
	{
		int id, w;
		cin >> id >> w;
		vv.pb(w);
		id--;
		int u = adj1[id].fi, v = adj1[id].se;
		if(depth[u] < depth[v])
			swap(u, v);
		cnt[0][u]++;
		query[u].pb(w);
	}
	vv.pb(0);
	sort(vv.begin(), vv.end());
	vv.erase(unique(vv.begin(), vv.end()), vv.end());
	version[1] = build(1, vv.size());
	DFS1(1);
	while(q--)
	{
		int u, v, x;
		ll y;
		cin >> u >> v >> x >> y;
		pii tmp = LCA(u, v);
		int dem = tmp.se, lca = tmp.fi;
		int ans = x - dem;
		ans += get(1, vv.size(), version[u], version[v], version[lca], y);
		ans = max(ans, -1ll);
		cout << ans << "\n";
	}
	re;
}

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