Submission #949840

#	Time	Username	Problem	Language	Result	Execution time	Memory
949840		lovrot	Two Currencies (JOI23_currencies)	C++17	100 / 100	1968 ms	239992 KiB

currencies

#include <cstdio> 
#include <vector> 
#include <algorithm> 

#define X first
#define Y second
#define PB push_back

using namespace std; 

typedef long long ll; 
typedef pair<int, ll> pil;
const int LOG = 17;
const int N = 1 << LOG;

struct node {
	node *l, *r;
	int cnt;
	ll upd;
	
	node() : l(NULL), r(NULL), cnt(0), upd(0) {}
	node(node *l, node *r, int cnt, ll upd) : l(l), r(r), cnt(cnt), upd(upd) {}
}; 

typedef node* pnode; 

int GET;
node T[3 * LOG * N]; 

pnode get(pnode u = NULL) { 
	if(u != NULL) {
		T[GET].l = u->l;
		T[GET].r = u->r;
		T[GET].cnt = u->cnt;
		T[GET].upd = u->upd;
	}
	return &T[GET++]; 
}

pnode update(int l, int r, ll val, pnode u = NULL, int lo = 0, int hi = N) {
	if(r <= lo || hi <= l) return u; 
	if(l <= lo && hi <= r) {
		pnode v = get(u);
		v->cnt += 1;
		v->upd += val;
		return v;
	}
	pnode v = get(u); 
	int mi = (lo + hi) / 2;
	if(u->l == NULL) u->l = get();
	if(u->r == NULL) u->r = get(); 
	v->l = update(l, r, val, u->l, lo, mi); 
	v->r = update(l, r, val, u->r, mi, hi); 
	return v;
}

int IV[N], MR[N], mrv; 
int UP[N][LOG], DEP[N];
vector<int> G[N]; 

pil query(int x, pnode u, int lo = 0, int hi = N) {
	if(u == NULL) return {0, 0};
	if(lo + 1 == hi) return {u->cnt, u->upd};
	int mi = (lo + hi) / 2;
	pil res = IV[x] < mi ? query(x, u->l, lo, mi) : query(x, u->r, mi, hi);
	return {res.X + u->cnt, res.Y + u->upd};
}

void dfs(int u, int p) { // DEP[1] = 1 !!!
	IV[u] = mrv++;
	for(int v : G[u]) 
		if(v != p) {
			DEP[v] = DEP[u] + 1;
			UP[v][0] = u;
			dfs(v, u);
		}
	MR[u] = mrv;
}

int lca(int u, int v) {
	if(DEP[u] > DEP[v]) swap(u, v);
	for(int i = LOG - 1; i >= 0; --i) 
		if(DEP[UP[v][i]] >= DEP[u]) v = UP[v][i];
	if(u == v) return u;
	for(int i = LOG - 1; i >= 0; --i) 
		if(UP[u][i] != UP[v][i]) {
			u = UP[u][i];
			v = UP[v][i];
		}
	return UP[u][0];
}

int A[N], B[N], P[N], C[N]; 
int I[N];
pnode RT[N];

pil query_path(int u, int v, int anc, int t) {
	pil ru = query(u, RT[t]), rv = query(v, RT[t]), ranc = query(anc, RT[t]);
//	if(u == 4 && v == 6) printf(">>> %d %d %lld\n", t, ranc.X, ranc.Y);
	return {ru.X + rv.X - 2 * ranc.X, ru.Y + rv.Y - 2 * ranc.Y};
}
	
int main() {
	int n, m, q;
	scanf("%d%d%d", &n, &m, &q);
	for(int i = 0; i < n - 1; ++i) {
		scanf("%d%d", A + i, B + i); 
		G[A[i]].PB(B[i]); 
		G[B[i]].PB(A[i]); 
	}
	for(int i = 1; i <= m; ++i) {
		I[i] = i;
		scanf("%d%d", P + i, C + i);
		--P[i];
	}

	sort(I + 1, I + m + 1, [&](int a, int b) { return C[a] < C[b]; });
	
	DEP[1] = 1;
	dfs(1, 0); 
	
	for(int i = 1; i < LOG; ++i) 
		for(int j = 1; j <= n; ++j) UP[j][i] = UP[UP[j][i - 1]][i - 1];

	RT[0] = get();
	for(int i = 1; i <= m; ++i) {
		int ind = I[i], p = P[ind], u = (DEP[A[p]] < DEP[B[p]] ? B[p] : A[p]);
		RT[i] = update(IV[u], MR[u], C[ind], RT[i - 1]);
//		printf("! %d[%d, %d] + %d\n", u, IV[u], MR[u], C[ind]);
	}
	
	for(; q--; ) {
		int s, t, x; 
		ll y;
		scanf("%d%d%d%lld", &s, &t, &x, &y); 

		int a = lca(s, t), lo = -1, hi = m + 1;
		for(; hi - lo > 1; ) {
			int mi = (lo + hi) / 2;
			pil res = query_path(s, t, a, mi);
//			if(q == 6) printf("%d: %d %lld\n", mi, res.X, res.Y);
			if(res.Y > y) hi = mi;
			else lo = mi;
		}

		pil res = query_path(s, t, a, lo), res_ = query_path(s, t, a, m);
//		printf("%d %d %d | %d\n", s, t, a, lo);
		printf("%d\n", max(-1, x - (res_.X - res.X)));
	}
	return 0;
}

Compilation message (stderr)

currencies.cpp: In function 'int main()':
currencies.cpp:105:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  105 |  scanf("%d%d%d", &n, &m, &q);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
currencies.cpp:107:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  107 |   scanf("%d%d", A + i, B + i);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~
currencies.cpp:113:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  113 |   scanf("%d%d", P + i, C + i);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~
currencies.cpp:135:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  135 |   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