Submission #891087

#	Time	Username	Problem	Language	Result	Execution time	Memory
891087		Cyber_Wolf	Two Currencies (JOI23_currencies)	C++17	0 / 100	5 ms	33368 KiB

currencies

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("Ofast")
 
using namespace std;
using namespace __gnu_pbds;
 
#define lg long long
#define ordered_set	tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define mid (lr+hr)/2
 
const lg N = 1e5+5;
 
vector<lg> adj[N], o[N];
vector<array<lg, 2>> updates(N);
lg euler[N], depth[N], anc[N][20], in[N], out[N], tmp, seg[N << 2][2], edges[N][2], que[N][4], low[N], high[N], best[N], ans[N];
 
/*
segtree: sum, cnt
queries: st, en, gold, silver
*/
 
void dfs(lg src)
{
	in[src] = ++tmp;
	euler[in[src]] = src;
	for(auto it : adj[src])
	{
		if(anc[src][0] == it)	continue;
		anc[it][0] = src;
		for(int i = 1; i < 20; i++)
		{
			if(anc[it][i-1] == -1)	break;
			anc[it][i] = anc[anc[it][i-1]][i-1];
		}
		depth[it] = depth[src]+1;
		dfs(it);
	}
	out[src] = tmp;
}
 
lg lca(lg a, lg b)
{
	if(depth[a] > depth[b])	swap(a, b);
	for(int i = 19; i+1; i--)
	{
		if(anc[b][i] == -1 || depth[anc[b][i]] < depth[a])	continue;
		b = anc[b][i];
	}
	if(a == b)	return a;
	for(int i = 19; i+1; i--)
	{
		if(anc[a][i] == -1 || anc[a][i] == anc[b][i])	continue;
		a = anc[a][i];
		b = anc[b][i];
	}
	return anc[a][0];
}
 
void build(lg node, lg lr, lg hr)
{
	if(lr == hr)
	{
		seg[node][0] = 0;
		seg[node][1] = 0;
		return;
	}
	build(node << 1, lr, mid);
	build(node << 1 | 1, mid+1, hr);
	seg[node][0] = 0;
	seg[node][1] = 0;
}
 
void update(lg node, lg lr, lg hr, lg idx, lg val)
{
	if(idx > hr || lr > idx)	return;
	if(lr == hr)
	{
		seg[node][0] += val;
		seg[node][1] += (val > 0 ? 1 : -1);
		return;
	}
	update(node << 1, lr, mid, idx, val);
	update(node << 1 | 1, mid+1, hr, idx, val);
	seg[node][0] = seg[node << 1][0]+seg[node << 1 | 1][0];
	seg[node][1] = seg[node << 1][1]+seg[node << 1 | 1][1];
	return;
}
 
array<lg, 2> get(lg node, lg lr, lg hr, lg lq, lg hq)
{
	if(lq > hr || lr > hq)	return {0, 0};
	if(lq <= lr && hr <= hq)	return {seg[node][0], seg[node][1]};
	array<lg, 2> ab = get(node << 1, lr, mid, lq, hq);
	array<lg, 2> cd = get(node << 1 | 1, mid+1, hr, lq, hq);
	ab[0] += cd[0];
	ab[1] += cd[1];
	return ab;
}
 
int main()
{
	fastio;
	lg n, m, q;
	cin >> n >> m >> q;
	for(int i = 1; i < n; i++)
	{
		lg u, v;
		cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
		edges[i][0] = u;
		edges[i][1] = v;
	}
	memset(anc, -1, sizeof(anc));
	dfs(1);
	for(int i = 1; i < n; i++)
	{
		if(depth[edges[i][0]] > depth[edges[i][1]])	swap(edges[i][0], edges[i][1]);
	}
	for(int i = 1; i <= m; i++)
	{
		lg a, b;
		cin >> a >> b;
		updates[i][0] = b;
		updates[i][1] = a;
	}
	sort(updates.begin()+1, updates.begin()+m+1);
	for(int i = 0; i < q; i++)
	{
		for(int j = 0; j < 4; j++)	cin >> que[i][j];
		low[i] = 0, high[i] = m;
	}
	bool changed = true;
	while(changed)
	{
		changed = false;
		build(1, 1, n);
		for(int i = 0; i < q; i++)
		{
			if(low[i] != high[i])	o[(low[i]+high[i]) >> 1].push_back(i);
		}
		for(int i = 0; i <= m; i++)
		{
			if(i)
			{
				update(1, 1, n, in[edges[updates[i][1]][1]], updates[i][0]);
				update(1, 1, n, out[edges[updates[i][1]][1]]+1, -updates[i][0]);
			}
			while(o[i].size())
			{
				lg idx = o[i].back();
				o[i].pop_back();
				lg _lca = lca(que[idx][0], que[idx][1]);
				array<lg, 2> ab = get(1, 1, n, 1, in[que[idx][0]]);
				array<lg, 2> cd = get(1, 1, n, 1, in[que[idx][1]]);
				array<lg, 2> ef = get(1, 1, n, 1, in[_lca]);
				if(ab[0]+cd[0]-2*ef[0] <= que[idx][3])
				{
					if(low[idx] != i+1)	changed = true;
					low[idx] = i+1;
					best[idx] = i;
				}
				else{
					if(high[idx] != i-1)	changed = true;
					high[idx] = i-1;
				}
			}
		}
	}
	build(1, 1, n);
	for(int i = 0; i < q; i++)	o[best[i]].push_back(i);
	for(int i = 1; i <= m; i++)
	{
		update(1, 1, n, in[edges[updates[i][1]][1]], updates[i][0]);
		update(1, 1, n, out[edges[updates[i][1]][1]]+1, -updates[i][0]);
		while(o[i].size())
		{
			lg idx = o[i].back();
			o[i].pop_back();
			lg _lca = lca(que[idx][0], que[idx][1]);
			array<lg, 2> ab = get(1, 1, n, 1, in[que[idx][0]]);
			array<lg, 2> cd = get(1, 1, n, 1, in[que[idx][1]]);
			array<lg, 2> ef = get(1, 1, n, 1, in[_lca]);
			ans[idx] = -(ab[1]+cd[1]-2*ef[1]);
		}
	}
	for(int i = 0; i < q; i++)
	{
		lg _lca = lca(que[i][0], que[i][1]);
		array<lg, 2> ab = get(1, 1, n, 1, in[que[i][0]]);
		array<lg, 2> cd = get(1, 1, n, 1, in[que[i][1]]);
		array<lg, 2> ef = get(1, 1, n, 1, in[_lca]);
		ans[i] += ab[1]+cd[1]-2*ef[1];
	}
	for(int i = 0; i < q; i++)
	{
		if(ans[i] > que[i][2])	cout << "-1\n";
		else	cout << ans[i] << '\n';
	}
	
 
    return 0;
}

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