Submission #1308102

#	Time	Username	Problem	Language	Result	Execution time	Memory
1308102		minh30082008	Two Currencies (JOI23_currencies)	C++20	0 / 100	4 ms	2112 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 node = ++dem;
	T[node] = T[old];
	if(l == r)
	{
		T[node].cnt++;
		T[node].sum += trueval[pos];
		return node;
	}
	int mid = (l + r) >> 1;
	if(pos <= mid)
	{
		T[node].l = update(l, mid, T[old].l, pos);
	}
	else
	{
		T[node].r = update(mid + 1, r, T[old].r, pos);
	}
	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;
		ver[v] = ver[u];
		for(auto x : query[v])
		{
			ver[v] = update(1, vv.size(), ver[v], x);
		}
		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];
}
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;
	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);
	}
	vv.pb(0);
	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());
	DFS1(1);
	while(q--)
	{
		ll u, v, x, y;
		cin >> u >> v >> x >> y;
		int lca = LCA(u, v);
		x += get(1, vv.size(), ver[u], ver[v], ver[lca], y);
		x -= T[ver[u]].cnt - T[ver[lca]].cnt + T[ver[v]].cnt - T[ver[lca]].cnt;
		if(x < 0)
			cout << "-1\n";
		else
			cout << x << "\n";
	}
	re;
}

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