Submission #792765

#	Time	Username	Problem	Language	Result	Execution time	Memory
792765		daoquanglinh2007	Two Currencies (JOI23_currencies)	C++17	100 / 100	945 ms	45676 KiB

currencies

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

#define int long long

const int NM = 1e5, LOG = 16;

struct checkpt{
	int v, c;
};

struct query{
	int id, s, t, lca, x, y, l, r, mid, res;
};

int N, M, Q, u[NM+5], v[NM+5], t = 0;
vector <int> adj[NM+5];
int parent[NM+5], h[NM+5], st[NM+5], en[NM+5];
int jump[NM+5][LOG+5];
checkpt a[NM+5];
query b[NM+5];
int bit[2*NM+5], bit2[2*NM+5];
int ans[NM+5];

void DFS(int u){
	st[u] = ++t;
	for (int i = 0; i < adj[u].size(); i++){
		int v = adj[u][i];
		if (h[v] != -1) continue;
		parent[v] = u;
		h[v] = h[u]+1;
		DFS(v);
	}
	en[u] = ++t;
}

void build(){
	for (int i = 1; i <= N; i++) jump[i][0] = parent[i];
	for (int j = 1; j <= LOG; j++)
		for (int i = 1; i <= N; i++)
			if (jump[i][j-1] != -1) jump[i][j] = jump[jump[i][j-1]][j-1];
			else jump[i][j] = -1;
}

int LCA(int u, int v){
	if (h[u] < h[v]) swap(u, v);
	for (int i = LOG; i >= 0; i--)
		if (h[u]-(1<<i) >= h[v]) u = jump[u][i];
	if (u == v) return u;
	for (int i = LOG; i >= 0; i--)
		if (jump[u][i] != -1 && jump[u][i] != jump[v][i]){
			u = jump[u][i];
			v = jump[v][i];
		}
	return parent[u];
}

bool cmp(checkpt a, checkpt b){
	return a.c < b.c;
}

bool cmp2(query a, query b){
	if (a.l > a.r) return 0;
	if (b.l > b.r) return 1;
	return a.mid < b.mid;
}

void update(int bit[NM+5], int p, int v){
	while (p <= 2*N){
		bit[p] += v;
		p += p & (-p);
	}
}

int get(int bit[NM+5], int p){
	int res = 0;
	while (p > 0){
		res += bit[p];
		p -= p & (-p);
	}
	return res;
}

int get_range(int bit[NM+5], int l, int r){
	return get(bit, r)-get(bit, l-1);
}

int get_path(int bit[NM+5], int s, int t, int lca){
	return get_range(bit, st[lca], st[s])+get_range(bit, st[lca], st[t])-2*get_range(bit, st[lca], st[lca]);
}

void pbs(){
	sort(b+1, b+1+Q, cmp2);
	memset(bit, 0, sizeof(bit));
	memset(bit2, 0, sizeof(bit2));
	for (int i = 1; i <= M; i++){
		update(bit, st[a[i].v], 1);
		update(bit, en[a[i].v], -1);
	}
	int j = 1;
	for (int i = 1; i <= Q; i++){
		if (b[i].l > b[i].r) break;
		while (j <= b[i].mid){
			update(bit, st[a[j].v], -1);
			update(bit, en[a[j].v], 1);
			update(bit2, st[a[j].v], a[j].c);
			update(bit2, en[a[j].v], -a[j].c);
			j++;
		}
		int tmp = get_path(bit2, b[i].s, b[i].t, b[i].lca);
		if (tmp <= b[i].y){
			b[i].res = get_path(bit, b[i].s, b[i].t, b[i].lca);
			b[i].l = b[i].mid+1;
		}
		else b[i].r = b[i].mid-1;
		
		b[i].mid = (b[i].l+b[i].r)/2;
	}
}

signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> N >> M >> Q;
	for (int i = 1; i < N; i++){
		cin >> u[i] >> v[i];
		adj[u[i]].push_back(v[i]);
		adj[v[i]].push_back(u[i]);
	}
	parent[1] = -1, h[1] = 0;
	for (int i = 2; i <= N; i++) h[i] = -1;
	DFS(1);
	build();
	for (int i = 1; i <= M; i++){
		int p; cin >> p;
		if (parent[v[p]] == u[p]) a[i].v = v[p]; else a[i].v = u[p];
		cin >> a[i].c;
	}
	sort(a+1, a+1+M, cmp);
	for (int i = 1; i <= Q; i++){
		b[i].id = i;
		cin >> b[i].s >> b[i].t >> b[i].x >> b[i].y;
		if (st[b[i].s] > st[b[i].t]) swap(b[i].s, b[i].t);
		b[i].lca = LCA(b[i].s, b[i].t);
		b[i].l = 0, b[i].r = M, b[i].mid = M/2;
	}
	for (int i = 0; (1<<i) <= M+1; i++)
		pbs();
	for (int i = 1; i <= Q; i++){
		if (b[i].res > b[i].x) ans[b[i].id] = -1;
		else ans[b[i].id] = b[i].x-b[i].res;
	}
	for (int i = 1; i <= Q; i++) cout << ans[i] << '\n';
	return 0;
}

Compilation message (stderr)

currencies.cpp: In function 'void DFS(long long int)':
currencies.cpp:27: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]
   27 |  for (int i = 0; i < adj[u].size(); i++){
      |                  ~~^~~~~~~~~~~~~~~

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