Submission #763261

#	Time	Username	Problem	Language	Result	Execution time	Memory
763261		MetalPower	Two Currencies (JOI23_currencies)	C++14	100 / 100	948 ms	39484 KiB

currencies

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

const int MX = 1e5 + 10;

#define ll long long
#define pii pair<int, int>
#define pli pair<ll, int>
#define fi first
#define se second

// parallel binser + hld

struct segtree{
	pli st[MX << 1];

	void build(){
		for(int i = 0; i < (MX << 1); i++) st[i] = {0ll, 0};
	}

	void upd(int p, int v){
		for(p += MX, st[p].fi += v, st[p].se += 1, p >>= 1; p > 0; p >>= 1){
			st[p].fi = st[p << 1].fi + st[p << 1|1].fi;
			st[p].se = st[p << 1].se + st[p << 1|1].se;
		}
	}

	pli que(int l, int r){
		pli res = {0, 0};
		for(l += MX, r += MX + 1; l < r; l >>= 1, r >>= 1){
			if(l & 1){
				res.fi += st[l].fi, res.se += st[l].se;
				l++;
			}
			if(r & 1){
				--r;
				res.fi += st[r].fi, res.se += st[r].se;
			}
		}
		return res;
	}
} S;

struct hld{
	int sz[MX], dep[MX], par[MX], in[MX], out[MX], head[MX], tim = 0;
	vector<int> adj[MX];

	void ae(int u, int v){
		adj[u].push_back(v);
		adj[v].push_back(u);
	}

	void dfs(int u, int v){
		if(v != 0) adj[u].erase(find(adj[u].begin(), adj[u].end(), v));

		par[u] = v;
		dep[u] = dep[v] + 1;
		sz[u] = 1;

		for(int& nx : adj[u]){
			dfs(nx, u);
			sz[u] += sz[nx];
			if(sz[nx] > sz[adj[u][0]]) swap(nx, adj[u][0]);
		}
	}

	void dfs2(int u, int v){
		in[u] = ++tim;
		for(int nx : adj[u]){
			if(nx == adj[u][0]) head[nx] = head[u];
			else head[nx] = nx;
			dfs2(nx, u);
		}
		out[u] = tim;
	}

	void init(){
		dfs(1, 0);
		head[1] = 1;
		dfs2(1, 0);
	}

	void upd(int nd, int v){
		S.upd(in[nd], v);
	}

	pli que(int u, int v){
		pli res = {0, 0};
		for(; head[u] != head[v]; v = par[head[v]]){
			if(dep[head[u]] > dep[head[v]]) swap(u, v);
			pli nw = S.que(in[head[v]], in[v]);
			res.fi += nw.fi, res.se += nw.se;
		}
		if(dep[u] > dep[v]) swap(u, v);
		pli nw = S.que(in[u] + 1, in[v]);
		res.fi += nw.fi, res.se += nw.se;
		return res;
	}
} H;

struct query{
	int s, t, x; ll y; int l, r, mid, id;

	query(int s = 0, int t = 0, int x = 0, ll y = 0, int l = 0, int r = 0, int id = 0) : 
		s(s), t(t), x(x), y(y), l(l), r(r), mid(l + r >> 1), id(id) {}

	bool operator < (const query other) const {
		return mid < other.mid;
	}
};

vector<query> queries[2];

int N, M, Q; pli ans[MX];
vector<pii> edges, ch;

int qs[MX], qt[MX], X[MX]; ll Y[MX];

int main(){
	ios_base::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;
		edges.push_back({u, v});
		H.ae(u, v);
	}

	for(int i = 0; i < M; i++){
		int p, c; cin >> p >> c; p--;
		ch.push_back({c, p});
	}

	sort(ch.begin(), ch.end());

	// cout << "init\n";
	H.init();

	for(int i = 0; i < N - 1; i++){
		if(H.dep[edges[i].fi] > H.dep[edges[i].se]) swap(edges[i].fi, edges[i].se);
	}

	for(int i = 0; i < Q; i++){
		int s, t, x; ll y; cin >> s >> t >> x >> y; qs[i] = s, qt[i] = t, X[i] = x, Y[i] = y;
		query curr = query(s, t, x, y, 0, M, i); 
		// 0 is none, 1 is index 0, 2 is index 0 to 1, ..., M is index 0 to M-1
		queries[0].push_back(curr);
	}

	int id = 0;
	sort(queries[0].begin(), queries[0].end());
	S.build();

	for(; !queries[id].empty(); ){
		int j = 0;
		// cout << "query " << id << '\n';
		for(query& curr : queries[id]){
			for(; j < M && j < curr.mid; j++) H.upd(edges[ch[j].se].se, ch[j].fi);
			pli nw = H.que(curr.s, curr.t);
			// cout << "at j " << curr.mid << " from " << curr.s << " to " << curr.t << " " << nw.fi << '\n';
			if(nw.fi <= curr.y){
				ans[curr.id] = nw;
				query nx = query(curr.s, curr.t, curr.x, curr.y, curr.mid + 1, curr.r, curr.id);
				if(nx.l <= nx.r) queries[id ^ 1].push_back(nx);
			}else{
				query nx = query(curr.s, curr.t, curr.x, curr.y, curr.l, curr.mid - 1, curr.id);
				if(nx.l <= nx.r) queries[id ^ 1].push_back(nx);
			}
		}
		queries[id].clear();
		id ^= 1;
		sort(queries[id].begin(), queries[id].end());
		S.build();
	}

	for(int i = 0; i < M; i++) H.upd(edges[ch[i].se].se, 1);

	for(int i = 0; i < Q; i++){
		// cout << "found " << ans[i].fi << " " << ans[i].se << '\n';
		int used_gold = H.que(qs[i], qt[i]).se - ans[i].se;
		assert(ans[i].fi <= Y[i]);
		if(used_gold > X[i]) cout << -1 << '\n';
		else cout << X[i] - used_gold << '\n';
	}
}

Compilation message (stderr)

currencies.cpp: In constructor 'query::query(int, int, int, long long int, int, int, int)':
currencies.cpp:105:45: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  105 |   s(s), t(t), x(x), y(y), l(l), r(r), mid(l + r >> 1), id(id) {}
      |                                           ~~^~~

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