Submission #1184952

#	Time	Username	Problem	Language	Result	Execution time	Memory
1184952		SmuggingSpun	Two Currencies (JOI23_currencies)	C++20	100 / 100	410 ms	103504 KiB

currencies

#include<bits/stdc++.h>
#define taskname "A"
using namespace std;
typedef long long ll;
const int lim = 1e5 + 5;
int n, m, q, u[lim], v[lim];
vector<int>g[lim], c[lim];
namespace sub1{
	void solve(){
		queue<int>Q;
		vector<int>h(n + 1, -1), parent(n + 1);
		vector<vector<int>>value(n + 1);
		Q.push(parent[1] = h[1] = 1);
		while(!Q.empty()){
			int s = Q.front();
			Q.pop();
			for(int& i : g[s]){
				int d = u[i] ^ v[i] ^ s;
				if(h[d] == -1){
					h[d] = h[parent[d] = s] + 1;
					value[d] = c[i];
					Q.push(d);
				}
			}
		}
		for(int _ = 0; _ < q; _++){
			int s, t, x;
			ll y;
			cin >> s >> t >> x >> y;
			vector<int>path_value;
			while(s != t){
				if(h[s] < h[t]){
					swap(s, t);
				}
				for(int& x : value[s]){
					path_value.emplace_back(x);
				}
				s = parent[s];
			}
			sort(path_value.begin(), path_value.end());
			int p = path_value.size();
			for(int i = 0; i < path_value.size(); i++){
				if((y -= path_value[i]) < 0){
					p = i;
					break;
				}
			}
			cout << max(-1, x - int(path_value.size()) + p) << "\n";
		}
	}
}
namespace sub23{
	struct Node{
		int lc, rc, cnt;
		ll sum;
		Node(){
			this->lc = this->rc = -1;
			this->cnt = 0;
			this->sum = 0;
		}	
	};
	vector<Node>st;
	void build(int id, int l, int r){
		if(l == r){
			return;
		}
		int m = (l + r) >> 1;
		st.emplace_back(Node());
		build(st[id].lc = int(st.size()) - 1, l, m);
		st.emplace_back(Node());
		build(st[id].rc = int(st.size()) - 1, m + 1, r);
	}
	void update(int id, int l, int r, int p, int x){
		st[id].sum += x;
		st[id].cnt++;
		if(l == r){
			return;
		}
		int m = (l + r) >> 1;
		if(m < p){
			st.emplace_back(st[st[id].rc]);
			update(st[id].rc = int(st.size()) - 1, m + 1, r, p, x);	
		}
		else{
			st.emplace_back(st[st[id].lc]);
			update(st[id].lc = int(st.size()) - 1, l, m, p, x);
		}
	}
	int h[lim], _c[lim], fc[lim], up[lim][17];
	void dfs(int s){
		for(int& i : g[s]){
			int d = u[i] ^ v[i] ^ s;
			if(d != up[s][0]){
				h[d] = h[up[d][0] = s] + 1;
				fc[d] = fc[s] + c[i].size();
				for(int i = 1; i < 17; i++){
					up[d][i] = up[up[d][i - 1]][i - 1];
				}
				st[d] = st[s];
				for(int& x : c[i]){
					update(d, 1, m, lower_bound(_c + 1, _c + m + 1, x) - _c, x);
				}
				dfs(d);
			}
		}
	}
	int lca(int u, int v){
		if(h[u] < h[v]){
			swap(u, v);
		}
		for(int i = 0, k = h[u] - h[v]; i < 17; i++){
			if(1 << i & k){
				u = up[u][i];
			}
		}
		if(u == v){
			return u;
		}
		for(int i = 16; i > -1; i--){
			if(up[u][i] != up[v][i]){
				u = up[u][i];
				v = up[v][i];
			}
		}
		return up[u][0];
	}
	void solve(){
		for(int i = 1, p = 0; i <= n; i++){
			for(int& x : c[i]){
				_c[++p] = x;
			}
		}
		sort(_c + 1, _c + m + 1);
		st.assign(n + 1, Node());
		build(1, 1, m);
		memset(up, fc[1] = 0, sizeof(up));
		dfs(h[1] = 1);
		for(int _ = 0; _ < q; _++){
			int s, t, x;
			ll y;
			cin >> s >> t >> x >> y;
			int p = lca(s, t), ids = s, idt = t, idp = p, l = 1, r = m, rem_cnt = 0;
			while(l < r){
				int m = (l + r) >> 1;
				ll left = st[st[ids].lc].sum + st[st[idt].lc].sum - (st[st[idp].lc].sum << 1LL);
				if(left <= y){
					y -= left;
					rem_cnt += st[st[ids].lc].cnt + st[st[idt].lc].cnt - (st[st[idp].lc].cnt << 1);
					ids = st[ids].rc;
					idt = st[idt].rc;
					idp = st[idp].rc;
					l = m + 1;
				}
				else{
					ids = st[ids].lc;
					idt = st[idt].lc;
					idp = st[idp].lc;
					r = m;
				}
			}
			cout << max(-1, x - fc[s] - fc[t] + (fc[p] << 1) + rem_cnt + (int)min(ll(st[ids].cnt + st[idt].cnt - (st[idp].cnt << 1)), y / _c[l])) << "\n";
		}
	}
}
int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	if(fopen(taskname".inp", "r")){
		freopen(taskname".inp", "r", stdin);
	}
	cin >> n >> m >> q;
	for(int i = 1; i < n; i++){
		cin >> u[i] >> v[i];
		g[u[i]].emplace_back(i);
		g[v[i]].emplace_back(i);
	}
	memset(c, 0, sizeof(c));
	for(int i = 0; i < m; i++){
		int p, x;
		cin >> p >> x;
		c[p].emplace_back(x);
	}
	if(max(max(n, m), q) <= 2000){
		sub1::solve();
	}
	else{
		sub23::solve();
	}
}

Compilation message (stderr)

currencies.cpp: In function 'int main()':
currencies.cpp:168:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  168 |                 freopen(taskname".inp", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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