제출 #1308093

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

currencies

#include<bits/stdc++.h>
#define fi first
#define se second
#define FOR(i, k, n) for(int i = k; i <= n; i++)
#define FOR1(i, k, n) for(int 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 "ALONE.inp"
#define output "ALONE.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;
const int base1 = 31;
const int SZ = 320;
const ll INF = 1e18;
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 ver[maxn], n, m, q;
int par[20][maxn], depth[maxn];
vi query[maxn];
pii canh[maxn];
int dem, ans;
struct smt{
	ll sum;
	int cnt, l, r;
} T[maxn * 25];
vi adj[maxn];
int trueval[maxn];
vi vv;
void DFS(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]];
		depth[v] = depth[u] + 1;
		DFS(v);
	}
}
int build(int l, int r)
{
	int node = ++dem;
	if(l == r)
	{
		T[node].l = T[node].r = T[node].sum = T[node].cnt = 0;
		return node;
	}
	int mid = (l + r) >> 1;
	T[node].l = build(l, mid);
	T[node].r = build(mid + 1, r);
	T[node].sum = T[node].cnt = 0;
	return node;
}
int update(int l, int r, int old, int pos, int val)
{
	int node = ++dem;
	T[node] = T[old];
	if(l == r)
	{
		T[node].cnt += val;
		T[node].sum += trueval[pos] * val;
		return node;
	}
	int mid = (l + r) >> 1;
	if(pos <= mid)
	{
		T[node].l = update(l, mid, T[old].l, pos, val);
	}
	else
	{
		T[node].r = update(mid + 1, r, T[old].r, pos, val);
	}
	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)
{
	ver[u] = ver[par[0][u]];
	for(auto x : query[u])
	{
		ver[u] = update(1, vv.size(), ver[u], x, 1);
	} 
	for(auto v : adj[u])
	{
		if(v == par[0][u])
			continue;
		DFS1(v);
	}
}
int LCA(int u, int v)
{
	if(depth[u] < depth[v])
		swap(u, v);
	int h = depth[u] - depth[v];
	FOR1(i, 18, 0)
		if((h >> i) & 1)
			u = par[i][u];
	if(u == v)
		return u;
	FOR(i, 18, 0)
		if(par[i][u] != par[i][v])
		{
			u = par[i][u];
			v = par[i][v];
		}
	return par[0][u];
}
void get(int l, int r, int lca, int u, int v, ll val)
{
	if(T[u].sum - T[lca].sum + T[v].sum - T[lca].sum <= val)
	{
		ans += T[u].cnt - T[lca].cnt + T[v].cnt - T[lca].cnt;
		return;
	}
	if(l == r)
	{
		ll sz = T[u].cnt - T[lca].cnt + T[v].cnt - T[lca].cnt;
		ll res = val / trueval[l];
		ans += min(res, sz);
		return;
	}
	int mid = (l + r) >> 1;
	if(T[T[u].l].sum - T[T[lca].l].sum + T[T[v].l].sum - T[T[lca].l].sum <= val)
	{
		ans += T[T[u].l].cnt - T[T[lca].l].cnt + T[T[v].l].cnt - T[T[lca].l].cnt;
		val -= T[T[u].l].sum - T[T[lca].l].sum + T[T[v].l].sum - T[T[lca].l].sum;
		get(mid + 1, r, T[lca].r, T[u].r, T[v].r, val);
	}
	else
	{
		get(l, mid, T[lca].l, T[u].l, T[v].l, val);
	}
	return;
}
signed main()
{
	fastio;
	cin >> n >> m >> q;
	FOR(i, 1, n - 1)
	{
		int u, v;
		cin >> u >> v;
		adj[u].pb(v);
		adj[v].pb(u);
		canh[i] = {u, v};
	}
	DFS(1);
	FOR(i, 1, m)
	{
		int id, w;
		cin >> id >> w;
		vv.pb(w);
		if(depth[canh[id].fi] < depth[canh[id].se])
			swap(canh[id].fi, canh[id].se);
		query[canh[id].fi].pb(w);
	}
	sort(vv.begin(), vv.end());
	vv.erase(unique(vv.begin(), vv.end()), vv.end());
	FOR(i, 1, n)
	{
		FOR(j, 0, (int)query[i].size() - 1)
		{
			int id = upper_bound(vv.begin(), vv.end(), query[i][j]) - vv.begin();
			trueval[id] = query[i][j];
			query[i][j] = id;
		}
	}
	ver[1] = build(1, vv.size());
	ver[0] = ver[1];
	DFS1(1);
	while(q--)
	{
		ll u, v, x, y;
		cin >> u >> v >> x >> y;
		int lca = LCA(u, v);
		ans = 0;
		get(1, vv.size(), ver[lca], ver[u], ver[v], y);
		x -= T[ver[u]].cnt - T[ver[lca]].cnt + T[ver[v]].cnt - T[ver[lca]].cnt;
		x += ans;
		if(x < 0)
			cout << "-1\n";
		else
			cout << x << "\n";
	}
	re;
}

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