Submission #972495

#	Time	Username	Problem	Language	Result	Execution time	Memory
972495		yellowtoad	Two Currencies (JOI23_currencies)	C++17	100 / 100	1421 ms	57432 KiB

currencies

#include <iostream>
#include <vector>
#include <algorithm>
#define f first
#define s second
#define int long long
using namespace std;

int n, m, q, p[100010][20], cnt, d[100010], ans[100010], vl[100010];
vector<int> edge[100010];
pair<pair<pair<int,int>,int>,pair<int,int>> qry[100010];
pair<int,int> edd[100010], ed[100010], rng[100010], node[400010], idk[100010];

void dfs(int u, int v, int depth) {
	p[u][0] = v;
	d[u] = depth;
	rng[u].f = ++cnt;
	for (int i = 1; i < 20; i++) p[u][i] = p[p[u][i-1]][i-1];
	for (int i = 0; i < edge[u].size(); i++) if (edge[u][i] != v) dfs(edge[u][i],u,depth+1);
	rng[u].s = cnt;
}

int lca(int u, int v) {
	if (d[u] < d[v]) swap(u,v);
	int i = 19;
	while (i >= 0) {
		if (d[p[u][i]] >= d[v]) u = p[u][i];
		i--;
	}
	if (u == v) return u;
	i = 19;
	while (i >= 0) {
		if (p[u][i] != p[v][i]) u = p[u][i], v = p[v][i];
		i--;
	}
	return p[u][0];
}

void split(int id) {
	node[id*2].f += node[id].f;
	node[id*2+1].f += node[id].f;
	node[id*2].s += node[id].s;
	node[id*2+1].s += node[id].s;
	node[id] = {0,0};
}

void update(int id, int x, int y, int l, int r, pair<int,int> val) {
	if ((l <= x) && (y <= r)) {
		node[id].f += val.f;
		node[id].s += val.s;
		return;
	}
	if ((r < x) || (y < l)) return;
	int mid = (x+y)/2;
	split(id);
	update(id*2,x,mid,l,r,val);
	update(id*2+1,mid+1,y,l,r,val);
}

pair<int,int> summ(int id, int x, int y, int pos) {
	if (x == y) return node[id];
	int mid = (x+y)/2;
	split(id);
	if (pos <= mid) return summ(id*2,x,mid,pos);
	else return summ(id*2+1,mid+1,y,pos);
}

pair<int,int> sum(int u) {
	return summ(1,1,n,rng[u].f);
}

void solve(int l, int r, vector<int> query) {
	vector<int> ll, rr;
	if (l == r) {
		for (int i = 0; i < query.size(); i++) {
			int u = qry[query[i]].f.f.f, v = qry[query[i]].f.f.s, lcaa = qry[query[i]].f.s;
			if (qry[query[i]].s.s < sum(u).f+sum(v).f-2*sum(lcaa).f) ll.push_back(query[i]);
			else ans[query[i]] = sum(u).s+sum(v).s-2*sum(lcaa).s;
		}
		for (int i = l; i <= r; i++) update(1,1,n,rng[ed[i].s].f,rng[ed[i].s].s,{-vl[i],1});
		for (int i = 0; i < ll.size(); i++) {
			int u = qry[ll[i]].f.f.f, v = qry[ll[i]].f.f.s, lcaa = qry[ll[i]].f.s;
			ans[ll[i]] = sum(u).s+sum(v).s-2*sum(lcaa).s;
		}
		for (int i = l; i <= r; i++) update(1,1,n,rng[ed[i].s].f,rng[ed[i].s].s,{vl[i],-1});
		return;
	}
	int mid = (l+r)/2;
	for (int i = mid+1; i <= r; i++) update(1,1,n,rng[ed[i].s].f,rng[ed[i].s].s,{-vl[i],1});
	for (int i = 0; i < query.size(); i++) {
		int u = qry[query[i]].f.f.f, v = qry[query[i]].f.f.s, lcaa = qry[query[i]].f.s;
		if (qry[query[i]].s.s < sum(u).f+sum(v).f-2*sum(lcaa).f) ll.push_back(query[i]);
		else rr.push_back(query[i]);
	}
	solve(l,mid,ll);
	for (int i = mid+1; i <= r; i++) update(1,1,n,rng[ed[i].s].f,rng[ed[i].s].s,{vl[i],-1});
	solve(mid+1,r,rr);
}

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> n >> m >> q;
	for (int i = 1; i < n; i++) {
		int u, v;
		cin >> u >> v;
		edd[i] = {u,v};
		edge[u].push_back(v);
		edge[v].push_back(u);
	}
	dfs(1,0,1);
	for (int i = 1; i <= m; i++) cin >> idk[i].s >> idk[i].f;
	sort(idk+1,idk+m+1);
	for (int i = 1; i <= m; i++) {
		int u = idk[i].s, v = idk[i].f;
		ed[i] = edd[u];
		vl[i] = v;
		if (d[ed[i].s] < d[ed[i].f]) swap(ed[i].f,ed[i].s);
		update(1,1,n,rng[ed[i].s].f,rng[ed[i].s].s,{vl[i],0});
	}
	for (int i = 1; i <= q; i++) {
		cin >> qry[i].f.f.f >> qry[i].f.f.s >> qry[i].s.f >> qry[i].s.s;
		qry[i].f.s = lca(qry[i].f.f.f,qry[i].f.f.s);
	}
	vector<int> query;
	for (int i = 1; i <= q; i++) query.push_back(i);
	solve(1,m,query);
	for (int i = 1; i <= q; i++) cout << max(-1LL,qry[i].s.f-ans[i]) << endl;
}

Compilation message (stderr)

currencies.cpp: In function 'void dfs(long long int, long long int, long long int)':
currencies.cpp:19:20: 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]
   19 |  for (int i = 0; i < edge[u].size(); i++) if (edge[u][i] != v) dfs(edge[u][i],u,depth+1);
      |                  ~~^~~~~~~~~~~~~~~~
currencies.cpp: In function 'void solve(long long int, long long int, std::vector<long long int>)':
currencies.cpp:75: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]
   75 |   for (int i = 0; i < query.size(); i++) {
      |                   ~~^~~~~~~~~~~~~~
currencies.cpp:81: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]
   81 |   for (int i = 0; i < ll.size(); i++) {
      |                   ~~^~~~~~~~~~~
currencies.cpp:90:20: 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]
   90 |  for (int i = 0; i < query.size(); i++) {
      |                  ~~^~~~~~~~~~~~~~

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