Submission #759335

#	Time	Username	Problem	Language	Result	Execution time	Memory
759335		aryan12	Two Currencies (JOI23_currencies)	C++17	100 / 100	4019 ms	45944 KiB

currencies

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

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

const int N = 1e5 + 5;
int n, m, q;
vector<int> g[N];
int bit[N], bit2[N];
int depth[N], tin[N], tout[N], tim = 0, dp[18][N];
vector<array<int, 2> > edges(N), checkpoints(N);
vector<array<int, 8> > queries(N);
// first 4 are queries values, next two left and right pointers for parallel binary search, second last is the answer
// last is the count of checkpoints for each query

struct BIT
{
	int bit[N];
	void init()
	{
		for(int i = 0; i < n + 5; i++)
		{
			bit[i] = 0;
		}
	}

	void update(int pos, int val)
	{
		if(pos == 0) return;
		for(int i = pos; i < n + 5; i += (i & (-i)))
		{
			bit[i] += val;
		}
	}

	int query(int pos)
	{
		if(pos == 0) return 0;
		int ans = 0;
		for(int i = pos; i > 0; i -= (i & (-i)))
		{
			ans += bit[i];
		}
		return ans;
	}
} cnt, value;

void dfs(int node, int par)
{
	dp[0][node] = par;
	tin[node] = ++tim;
	for(int to: g[node])
	{
		if(to == par) continue;
		depth[to] = depth[node] + 1;
		dfs(to, node);
	}
	tout[node] = tim;
}

int LCA(int u, int v)
{
	if(depth[u] < depth[v])
	{
		swap(u, v);
	}
	int diff = depth[u] - depth[v];
	for(int i = 17; i >= 0; i--)
	{
		if((1 << i) & diff)
		{
			u = dp[i][u];
		}
	}
	if(u == v) return u;
	for(int i = 17; i >= 0; i--)
	{
		if(dp[i][v] != dp[i][u])
		{
			v = dp[i][v];
			u = dp[i][u];
		}
	}
	return dp[0][v];
}

void Solve() 
{
	cin >> n >> m >> q;
	for(int i = 1; i < n; i++)
	{
		int u, v;
		cin >> u >> v;
		g[u].push_back(v);
		g[v].push_back(u);
		edges[i] = {u, v};
	}
	cnt.init();
	value.init();
	dfs(1, -1);
	// for(int i = 1; i <= n; i++)
	// {
	// 	cout << "i = " << i << ", " << tin[i] << " " << tout[i] << "\n";
	// }
	for(int i = 1; i < 18; i++)
	{
		for(int j = 1; j <= n; j++)
		{
			dp[i][j] = ((dp[i - 1][j] == -1) ? -1 : dp[i - 1][dp[i - 1][j]]);
		}
	}
	for(int i = 1; i <= m; i++)
	{
		cin >> checkpoints[i][0] >> checkpoints[i][1];
	}
	sort(checkpoints.begin() + 1, checkpoints.begin() + 1 + m, [](array<int, 2> a, array<int, 2> b)
	{
		return a[1] < b[1];
	});
	for(int i = 1; i <= m; i++)
	{
		int edge_idx = checkpoints[i][0];
		// cout << "edge_idx = " << edge_idx << endl;
		int node = (depth[edges[edge_idx][0]] > depth[edges[edge_idx][1]]) ? edges[edge_idx][0] : edges[edge_idx][1];
		// cout << "node = " << node << endl;
		cnt.update(tin[node], 1);
		cnt.update(tout[node] + 1, -1);
		// cout << "update(" << tin[node] << ", 1)\n";
		// cout << "update(" << tout[node] + 1 << ", -1)\n";
	}
	// for(int i = 1; i <= n; i++)
	// {
	// 	cout << "i = " << i << ", cnt = " << cnt.query(i) << endl;
	// }
	for(int i = 1; i <= q; i++)
	{
		cin >> queries[i][0] >> queries[i][1] >> queries[i][2] >> queries[i][3];
		queries[i][4] = 0;
		queries[i][5] = m;
		queries[i][6] = -1;
		queries[i][7] = cnt.query(tin[queries[i][0]]) + cnt.query(tin[queries[i][1]]) - 2 * cnt.query(tin[LCA(queries[i][0], queries[i][1])]);
		// cout << "LCA = " << LCA(queries[i][0], queries[i][1]) << "\n";
		// cout << "queries[i][7] = " << queries[i][7] << "\n";
	}
	while(true)
	{
		cnt.init();
		value.init();
		vector<int> queries_mid[m + 1];
		int counter = 0;
		for(int i = 1; i <= q; i++)
		{
			if(queries[i][4] > queries[i][5])
			{
				counter++;
				continue;
			}
			int mid = (queries[i][4] + queries[i][5]) / 2;
			// cout << "query number = " << i << ", middle value = " << mid << "\n";
			queries_mid[mid].push_back(i);
		}
		if(counter == q)
		{
			break;
		}
		for(int i = 0; i <= m; i++)
		{
			for(int j = 0; j < queries_mid[i].size(); j++)
			{
				int index = queries_mid[i][j];
				// cout << "checkpoint number = " << i << ", index = " << index << endl;
				int lca = LCA(queries[index][0], queries[index][1]);
				int total_value = (value.query(tin[queries[index][0]]) + value.query(tin[queries[index][1]]) - 2 * value.query(tin[lca]));
				int total_count = (cnt.query(tin[queries[index][0]]) + cnt.query(tin[queries[index][1]]) - 2 * cnt.query(tin[lca]));
				// cout << "total_value = " << total_value << ", total_count = " << total_count << endl;
				if(total_value <= queries[index][3])
				{
					queries[index][6] = (queries[index][2] >= queries[index][7] - total_count) ? (queries[index][2] - (queries[index][7] - total_count)) : (-1);
					queries[index][4] = i + 1;
				}
				else
				{
					queries[index][5] = i - 1;
				}
			}
			if(i != m)
			{
				int edge_idx = checkpoints[i + 1][0];
				int node = (depth[edges[edge_idx][0]] > depth[edges[edge_idx][1]]) ? edges[edge_idx][0] : edges[edge_idx][1];
				// cout << "edge_idx = " << edge_idx << ", node = " << node << "\n";
				cnt.update(tin[node], 1);
				cnt.update(tout[node] + 1, -1);
				value.update(tin[node], checkpoints[i + 1][1]);
				value.update(tout[node] + 1, -checkpoints[i + 1][1]);
				// for(int j = 1; j <= n; j++)
				// {
				// 	cout << "j = " << j << ", cnt = " << cnt.query(j) << endl;
				// }
				// for(int j = 1; j <= n; j++)
				// {
				// 	cout << "j = " << j << ", value = " << value.query(j) << endl;
				// }
			}
		}
	}
	for(int i = 1; i <= q; i++)
	{
		cout << queries[i][6] << "\n";
	}
}

int32_t main() 
{
	auto begin = std::chrono::high_resolution_clock::now();
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int t = 1;
	// cin >> t;
	for(int i = 1; i <= t; i++) 
	{
		//cout << "Case #" << i << ": ";
		Solve();
	}
	auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
	return 0;
}

Compilation message (stderr)

currencies.cpp: In function 'void Solve()':
currencies.cpp:169:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  169 |    for(int j = 0; j < queries_mid[i].size(); j++)
      |                   ~~^~~~~~~~~~~~~~~~~~~~~~~

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