Submission #891106

#	Time	Username	Problem	Language	Result	Execution time	Memory
891106		Cyber_Wolf	Two Currencies (JOI23_currencies)	C++17	100 / 100	2227 ms	68808 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, bit1[N], bit2[N], edges[N][2], que[N][4], low[N], high[N], best[N], ans[N];
lg n, m, q;

/*
BIT: 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 update(lg idx, lg val)
{
	for(; idx <= n; idx += (idx&(-idx)))	
	{
		bit1[idx] += val;
		bit2[idx] += (val < 0 ? -1 : 1);
	}
	return;
}
 
array<lg, 2> get(lg idx)
{
	array<lg, 2> ab = {0, 0};
	for(; idx; idx -= (idx&(-idx)))	ab[0] += bit1[idx], ab[1] += bit2[idx];
	return ab;
}
 
int main()
{
	fastio;
	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;
		for(int i = 1; i <= n; i++)	bit1[i] = bit2[i] = 0;
		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(in[edges[updates[i][1]][1]], updates[i][0]);
				update(out[edges[updates[i][1]][1]]+1, -updates[i][0]);
			}
			while(o[i].size())
			{
				changed = true;
				lg idx = o[i].back();
				o[i].pop_back();
				lg _lca = lca(que[idx][0], que[idx][1]);
				array<lg, 2> ab = get(in[que[idx][0]]);
				array<lg, 2> cd = get(in[que[idx][1]]);
				array<lg, 2> ef = get(in[_lca]);
				if(ab[0]+cd[0]-2*ef[0] <= que[idx][3])
				{
					low[idx] = i+1;
					best[idx] = i;
				}
				else{
					high[idx] = i-1;
				}
			}
		}
	}
	for(int i = 1; i <= n; i++)	bit1[i] = bit2[i] = 0;
	for(int i = 0; i < q; i++)	o[best[i]].push_back(i);
	for(int i = 1; i <= m; i++)
	{
		update(in[edges[updates[i][1]][1]], updates[i][0]);
		update(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(in[que[idx][0]]);
			array<lg, 2> cd = get(in[que[idx][1]]);
			array<lg, 2> ef = get(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(in[que[i][0]]);
		array<lg, 2> cd = get(in[que[i][1]]);
		array<lg, 2> ef = get(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 << que[i][2]-ans[i] << '\n';
	}
	
    return 0;
}

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