Submission #979046

#	Time	Username	Problem	Language	Result	Execution time	Memory
979046		temporary1	Two Currencies (JOI23_currencies)	C++14	100 / 100	2950 ms	207420 KiB

currencies

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

#define f first
#define s second

struct node {
	long long val;
	int cnt;
	node *left, *right;
	node(long long val, int cnt, node* left, node *right) : val(val), cnt(cnt), left(left), right(right) {};
};
node *perstree[100001];
int in[100001];
int out[100001];
int height[100001];
int bl[100001][20];
pair<int,int> edges[100001];
vector<pair<int,int>> graph[100001];
vector<pair<int,int>> vctr;
int n;
int total[100001];
int borders[100001];

long long getval(node *n) {
	if (n)return n->val;
	else return 0;
}

int getcnt(node *n) {
	if (n)return n->cnt;
	else return 0;
}

node* build(int a, int b) {
	if (a > b)return NULL;
	if (a == b) {
		return new node(0,0,NULL,NULL);
	}
	return new node(0,0,build(a,(a+b)/2),build((a+b)/2+1,b));
}

node* update(node *n, int a, int b, int x, long long v, int c) {
	// printf("%d %d %d %lld\n",a,b,x,v);
	if (a > b)return NULL;
	if (a == b) {
		// printf("%d : %lld + %lld , %d + %d\n",a,n->val,v,n->cnt,c);
		return new node(n->val+v,n->cnt+c,NULL,NULL);
	}
	node* nleft;
	node* nright;
	if (x <= (a+b)/2) {
		nleft = update(n->left,a,(a+b)/2,x,v,c);
		nright = n->right;
	} else if (x >= (a+b)/2+1) {
		nright = update(n->right,(a+b)/2+1,b,x,v,c);
		nleft = n->left;
	}
	// printf("%d-%d : %lld -> %lld , %d -> %d\n",a,b,n->val,getval(nleft)+getval(nright),n->cnt,getcnt(nleft)+getcnt(nright));
	return new node(getval(nleft)+getval(nright),getcnt(nleft)+getcnt(nright),nleft,nright);
}

pair<long long,int> query(node *n, int a, int b, int x, int y) {
	if (a > b || b < x || y < a)return {0,0};
	if (x <= a && b <= y) {
		// printf("%d=%d : %lld , %d\n",a,b,n->val,n->cnt);
		return {n->val,n->cnt};
	}
	pair<long long,int> qleft, qright;
	if (y <= (a+b)/2) {
		qleft = query(n->left,a,(a+b)/2,x,y);
		qright = {0,0};
	} else if (x >= (a+b)/2+1) {
		qright = query(n->right,(a+b)/2+1,b,x,y);
		qleft = {0,0};
	} else {
		qleft = query(n->left,a,(a+b)/2,x,y);
		qright = query(n->right,(a+b)/2+1,b,x,y);
	}
	// printf("%d==%d %d %d: %lld , %d\n",a,b,x,y,qleft.f+qright.f,qleft.s+qright.s);
	return {qleft.f+qright.f,qleft.s+qright.s};
}

void findsize(int node, int pa, int h) {
	height[node] = h;
	if (pa != -1) {
		bl[node][0] = pa;
	}
	if (pa != -1)bl[node][0] = pa;
	for (auto it : graph[node]) {
		if (it.f == pa)continue;
		findsize(it.f,node,h+1);
	}
	return;
}

void findborders(int node, int pa, int b) {
	total[node] = b;
	for (auto it : graph[node]) {
		if (it.f == pa)continue;
		findborders(it.f,node,b+borders[it.f]);
	}
	return;
}

int timer = 1;
void eulertour(int node, int pa) {
	in[node] = timer;
	++timer;
	for (auto it : graph[node]) {
		if (it.f == pa) {
			edges[it.s] = {it.f,node};
			continue;
		}
		eulertour(it.f,node);
	}
	out[node] = timer;
	return;
}

int findlca(int a, int b) {
	if (height[a] != height[b]) {
		if (height[b] < height[a]) {
			swap(a,b);
		}
		for (int dist = height[b]-height[a]; dist > 0; dist -= dist&-dist) {
			b = bl[b][(int)log2(dist&-dist)];
		}
	}
	int cap1 = floor(log2(n));
	for (;a != b;) {
		int l = -1;
		int r = cap1;
		for (;;) {
			if (l >= r)break;
			int m = (l+r+1)/2;
			if (bl[a][m] == bl[b][m]) {
				r = m-1;
			} else {
				l = m;
			}
		}
		if (l == -1) {
			l = 0;
		}
		a = bl[a][l];
		b = bl[b][l];
		cap1 = l-1;
	}
	return a;
}

pair<long long,int> path(int amt, int u, int v, int lca) {
	pair<long long,int> qu, qv, qlca;
	qu = query(perstree[amt],1,n+1,1,in[u]);
	qv = query(perstree[amt],1,n+1,1,in[v]);
	qlca = query(perstree[amt],1,n+1,1,in[lca]);
	// printf("%lld %d %lld %d %lld %d\n",qu.f,qu.s,qv.f,qv.s,qlca.f,qlca.s);
	return {qu.f+qv.f-2*qlca.f,qu.s+qv.s-2*qlca.s};
}

int tcoins(int u, int v, int lca) {
	return total[u]+total[v]-2*total[lca];
}

int main() {
	int m, q;
	scanf("%d%d%d",&n,&m,&q);
	for (int i = 1; i <= n-1; ++i) {
		int a, b;
		scanf("%d%d",&a,&b);
		graph[a].push_back({b,i});
		graph[b].push_back({a,i});
	}
	for (int i = 0; i < m; ++i) {
		int p, c;
		scanf("%d%d",&p,&c);
		vctr.push_back({c,p});
	}
	vctr.push_back({-1,-1});
	sort(vctr.begin(),vctr.end());
	findsize(1,-1,0);
	eulertour(1,-1);
	for (auto it : vctr) {
		++borders[edges[it.s].s];
		// printf("added %d\n",edges[it.s].s);
	}
	findborders(1,-1,0);
	// for (int i = 1; i <= n; ++i) {
		// printf("%d -> %d\n",in[i],out[i]);
	// }
	// for (int j = 1; j <= n; ++j) {
		// printf("%d ",total[j]);
	// }
	// printf("\n");
	for (int k = 1; k <= 19; ++k) {
		for (int i = 1; i <= n; ++i) {
			bl[i][k] = bl[bl[i][k-1]][k-1];
		}
	}
	perstree[0] = build(1,n+1);
	// for (int j = 1; j <= n; ++j) {
		// printf("[%lld] ",query(perstree[0],1,n+1,1,in[j]).f);
	// }
	// printf("\n\n");
	for (int i = 1; i <= m; ++i) {
		// printf("%d %d : %d %d\n",edges[vctr[i].s].s,in[edges[vctr[i].s].s],edges[vctr[i].s].f,out[edges[vctr[i].s].s]);
		perstree[i] = update(perstree[i-1],1,n+1,in[edges[vctr[i].s].s],vctr[i].f,1);
		perstree[i] = update(perstree[i],1,n+1,out[edges[vctr[i].s].s],-vctr[i].f,-1);
		for (int j = 1; j <= n; ++j) {
			// printf("[%lld] ",query(perstree[i],1,n+1,1,in[j]).f);
		}
		// printf("\n\n");
	}
	// for (int i = 0; i <= m; ++i) {
	// 	for (int j = 1; j <= n; ++j) {
			// printf("%lld ",query(perstree[i],1,n+1,1,in[j]).f);
	// 	}
		// printf("\n");
	// }
	for (int qi = 0; qi < q; ++qi) {
		int s, t, x;
		long long y;
		scanf("%d%d%d%lld",&s,&t,&x,&y);
		int l = 0, r = m;
		int lca = findlca(s,t);
		// printf("\n%d %d lca: %d\n",s,t,lca);
		while (true) {
			if (l >= r)break;
			int mid = (l+r+1)/2;
			long long cost = path(mid,s,t,lca).f;
			// printf("%d %lld\n",mid,cost);
			if (cost <= y) {
				l = mid;
			} else {
				r = mid-1;
			}
		}
		// printf("%d !\n\n",l);
		int coins = path(l,s,t,lca).s;
		int totalcoins = tcoins(s,t,lca);
		int pay = totalcoins-coins;
		// printf("%d %d %d\n",coins,totalcoins,pay);
		if (pay <= x) {
			printf("%d\n",x-pay);
		} else {
			printf("-1\n");
		}
	}
	return 0;
}

Compilation message (stderr)

currencies.cpp: In function 'int main()':
currencies.cpp:168:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  168 |  scanf("%d%d%d",&n,&m,&q);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~
currencies.cpp:171:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  171 |   scanf("%d%d",&a,&b);
      |   ~~~~~^~~~~~~~~~~~~~
currencies.cpp:177:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  177 |   scanf("%d%d",&p,&c);
      |   ~~~~~^~~~~~~~~~~~~~
currencies.cpp:224:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  224 |   scanf("%d%d%d%lld",&s,&t,&x,&y);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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