Submission #1209517

#	Time	Username	Problem	Language	Result	Execution time	Memory
1209517		duckindog	Two Currencies (JOI23_currencies)	C++17	10 / 100	5095 ms	38596 KiB

currencies

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N = 100'000 + 10;
int n, m, q;
pair<int, int> edge[N];
struct CP { 
	int p, c;
	friend istream& operator >> (istream& is, CP& rhs) { 
		return is >> rhs.p >> rhs.c;
	}
} cp[N];
struct Query { 
	int s, t, x, y;
	friend istream& operator >> (istream& is, Query& rhs) { 
		return is >> rhs.s >> rhs.t >> rhs.x >> rhs.y;
	}
} query[N];

vector<int> ad[N];

int f[N][17];
int st[N], ed[N], num;
void dfs(int u, int p = -1) { 
	st[u] = ++num;

	for (int i = 1; i <= 16; ++i) f[u][i] = f[f[u][i - 1]][i - 1];
	for (const auto& v : ad[u]) { 
		if (v == p) continue;
		f[v][0] = u;
		dfs(v, u);
	}

	ed[u] = num;
}
inline bool anc(int u, int v) { return st[u] <= st[v] && ed[u] >= ed[v]; }
int lca(int u, int v) { 
	if (anc(u, v)) return u;
	if (anc(v, u)) return v;
	
	for (int i = 16; i >= 0; --i)
		if (!anc(f[u][i], v)) u = f[u][i];
	return f[u][0];
}

vector<int> save[N];

int32_t main() { 
	cin.tie(0)->sync_with_stdio(0);

	cin >> n >> m >> q;
	for (int i = 1; i < n; ++i) cin >> edge[i].first >> edge[i].second;
	for (int i = 1; i <= m; ++i) cin >> cp[i];
	for (int i = 1; i <= q; ++i) cin >> query[i];

	for (int i = 1; i < n; ++i) { 
		const auto& [u, v] = edge[i];
		ad[u].push_back(v);
		ad[v].push_back(u);
	}
	dfs(f[1][0] = 1);

	for (int i = 1; i < n; ++i) { 
		auto& [u, v] = edge[i];
		if (anc(v, u)) swap(u, v);
	}

	for (int i = 1; i <= m; ++i) { 
		const auto& [p, c] = cp[i];
		save[edge[p].second].push_back(i);
	}

	for (int i = 1; i <= q; ++i) { 
		auto [s, t, x, y] = query[i];

		vector<int> allCP;
		for (int u = s; !anc(u, t); u = f[u][0]) { 
			allCP.insert(allCP.end(), save[u].begin(), save[u].end());
		}
		for (int u = t; !anc(u, s); u = f[u][0]) { 
			allCP.insert(allCP.end(), save[u].begin(), save[u].end());
		}

		sort(allCP.begin(), allCP.end(), [&](int x, int y) { 
			return cp[x].c < cp[y].c;
		});
		
		for (const auto& idx : allCP) { 
			const auto& [p, c] = cp[idx];

			if (y >= c) y -= c;
			else x -= 1;
		}

		if (x < 0) cout << -1 << "\n";
		else cout << x << "\n";
	}
}

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