Submission #1308148

#	Time	Username	Problem	Language	Result	Execution time	Memory
1308148		sweetwibu2k8	Two Currencies (JOI23_currencies)	C++20	100 / 100	573 ms	30312 KiB

currencies

#include <bits/stdc++.h>
using namespace std;

#define endl "\n"
#define fi first
#define se second
#define pb push_back
#define p_q priority_queue
#define bit(n, i) (((n)>>(i))&1)
#define all(x) x.begin(), x.end()

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,int> pli;
typedef vector <vector <int> > vvi;

const int M = 1e5 + 6;
const int mod = 1e9 + 7;
const int inf = 1e9 + 7;

void maximize (int &a, int b) { if (a < b) a = b; }
void minimize (int &a, int b) { if (a > b) a = b; }
void add (int &a, int b) { a += b; if (a >= mod) a -= mod; }
void del (int &a, int b) { a -= b; if (a < 0) a += mod; }

int n, m, q;
vector <int> g[M];
pii e[M], t[M];
int cost[M], in[M], out[M], tt[M], dem[M];
int anc[M][18], depth[M];
int d[M], ini[M], Lca[M];
int timedfs = 0;
int L[M], R[M], MID[M];
ll ans[M];
struct query 
{
	int s, t;
	ll x, y;
} Q[M];

struct Fenwick
{
	ll f[M];
	int n;
	
	void resize (int x) { n = x; for (int i = 1; i <= n; i ++) f[i] = 0; }
	void update (int i, int val) { while (i <= n) { f[i] += val; i += i & (-i); } }
	ll GET (int i) { ll res = 0; while (i > 0) { res += f[i]; i -= i & (-i); } return res; }
	ll get (int l, int r) { return GET (r) - GET (l - 1); }
} BIT, CNT;

void dfs (int u, int parent)
{
	in[u] = ++ timedfs;
	tt[timedfs] = u;
	
	for (int &v : g[u])
	{
		if (v == parent) continue;
		anc[v][0] = u;
		depth[v] = depth[u] + 1;
		dfs (v, u);
	}
	
	out[u] = timedfs;
}

int LCA (int u, int v)
{
	if (depth[u] < depth[v]) swap (u, v);
	while (depth[u] > depth[v])
	{
		int k = __lg (depth[u] - depth[v]);
		u = anc[u][k];
	}
	if (u == v) return u;
	
	int k = __lg (depth[u]);
	while (k >= 0)
	{
		if (anc[u][k] != anc[v][k])
		{
			u = anc[u][k];
			v = anc[v][k];
		}
		k --;
	}
	return anc[u][0];
}

void prework (int u, int parent)
{
	for (int &v : g[u])
	{
		if (v == parent) continue;
		d[v] += d[u];
		prework (v, u);
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
//	freopen (".inp", "r", stdin);
//	freopen (".out", "w", stdout);
	
	cin >> n >> m >> q;
	for (int i = 1; i < n; i ++)
	{
		int u, v; cin >> u >> v;
		g[u].pb (v);
		g[v].pb (u);
		e[i] = {u, v};
	}
	for (int i = 1; i <= m; i ++)
	{
		int p, c; cin >> p >> c;
		t[i] = {c, p};
	}
	
	for (int i = 1; i <= q; i ++)
	{
		int s, t; ll x, y; cin >> s >> t >> x >> y;
		Q[i] = {s, t, x, y};
		ans[i] = -1;
	}
	
	dfs (1, 0);
	int kmax = __lg (n);
	for (int k = 1; k <= kmax; k ++)
		for (int i = 1; i <= n; i ++)
			anc[i][k] = anc[anc[i][k - 1]][k - 1];
	for (int i = 1; i < n; i ++)
		if (e[i].fi != anc[e[i].se][0]) swap (e[i].fi, e[i].se);
	
	sort (t + 1, t + m + 1);
	for (int i = 1; i <= m; i ++)
	{
		int id = e[t[i].se].se;
		d[id] ++;
	}
		
	prework (1, 0);
	for (int i = 1; i <= q; i ++)
	{
		int u = Q[i].s, v = Q[i].t;
		int lca = LCA (u, v);
		ini[i] = d[u] + d[v] - 2 * d[lca];
		Lca[i] = lca;
	}
	
	for (int i = 1; i <= q; i ++)
		L[i] = 0, R[i] = m;
	
	while (true)
	{
		vector <int> Query;
		for (int i = 1; i <= q; i ++)
		{
			if (L[i] > R[i]) continue;
			MID[i] = (L[i] + R[i]) / 2;
			Query.pb (i);
		}
		
		if (Query.empty()) break;
		sort (all (Query), [] (int a, int b) {
			return MID[a] < MID[b];
		});
		
		
		BIT.resize (n + 2);
		CNT.resize (n + 2);
		int pt = 1;
		for (int &i : Query)
		{
			int ss = Q[i].s, tt = Q[i].t;
			ll x = Q[i].x, y = Q[i].y;
			while (pt <= MID[i])
			{
				int v = e[t[pt].se].se, val = t[pt].fi;
				BIT.update (in[v], val);
				BIT.update (out[v] + 1, -val);
				CNT.update (in[v], 1);
				CNT.update (out[v] + 1, -1);
				pt ++;
			}
			ll lmao = BIT.GET (in[ss]) + BIT.GET (in[tt]) - 2 * BIT.GET (in[Lca[i]]);
			ll sl = CNT.GET (in[ss]) + CNT.GET (in[tt]) - 2 * CNT.GET (in[Lca[i]]);
			if (lmao <= y)
			{
				ans[i] = max (ans[i], x - ini[i] + sl);
				L[i] = MID[i] + 1;
			}
			else R[i] = MID[i] - 1;
		}
	}
	
	for (int i = 1; i <= q; i ++)
		cout << ans[i] << endl;
	return 0;
}

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