Submission #1247316

#	Time	Username	Problem	Language	Result	Execution time	Memory
1247316		khoianh	Two Currencies (JOI23_currencies)	C++20	100 / 100	508 ms	60428 KiB

currencies

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mn = 1e5 + 5;
ll n, m, q, x, y, e1[mn], e2[mn], t = 0, in[mn], out[mn], l[mn], r[mn], jump[mn][21], bit[mn], a[mn], ans[mn], b[mn], c[mn], d[mn], mid[mn], lc[mn];
pair<ll, ll> p[mn];
vector<ll> v[mn], que[mn];

void build(){
	for(int i = 0; i <= 2 * n; ++i) bit[i] = 0;
	return;
}

void update(ll i, ll val){
	for(; i <= 2 * n; i = i | (i + 1)) bit[i] += val;
	return;
}

ll get(ll r){
	ll ret = 0;
	for(; r >= 0; r = (r & (r + 1)) - 1) ret += bit[r];
	return ret;	
}

void dfs(ll i, ll parent){
	in[i] = ++t;
	jump[i][0] = parent;
	for(int j = 1; j <= 20; ++j) jump[i][j] = jump[jump[i][j - 1]][j - 1];
	for(auto j : v[i]){
		if(parent == j) continue;
		dfs(j, i);
	}
	out[i] = ++t;
	return;
}

bool anc(ll u, ll v){
	return in[u] <= in[v] && out[v] <= out[u];
}

ll lca(ll u, ll v){
	if(anc(u, v)) return u;
	if(anc(v, u)) return v;
	for(int i = 20; i >= 0; --i){
		if(!anc(jump[u][i], v)) u = jump[u][i];
	}
	return jump[u][0];
}

void solve(){
	cin >> n >> m >> q;
	for(int i = 1; i < n; ++i) cin >> e1[i] >> e2[i], v[e1[i]].push_back(e2[i]), v[e2[i]].push_back(e1[i]);
	for(int i = 1; i <= m; ++i) cin >> p[i].second >> p[i].first;
	sort(p + 1, p + m + 1);
	dfs(1, 1);
	for(int i = 1; i <= q; ++i) cin >> a[i] >> b[i] >> c[i] >> d[i], l[i] = 1, r[i] = m, lc[i] = lca(a[i], b[i]);
	for(int i = 1; i < n; ++i){
		if(jump[e1[i]][0] == e2[i]) swap(e1[i], e2[i]);
	} 
	while(true){
		ll ok = q;
		for(int i = 1; i <= q; ++i){
			if(l[i] > r[i]) --ok;
			else mid[i] = (l[i] + r[i]) / 2, que[mid[i]].push_back(i);
		}
		if(!ok) break;
		build();
		for(int i = 1; i <= m; ++i){
			update(in[e2[p[i].second]], p[i].first);
			update(out[e2[p[i].second]], 0 - p[i].first);
			for(ll j : que[i]){
				ll s = get(in[a[j]]) + get(in[b[j]]) - 2 * get(in[lc[j]]);
				if(s <= d[j]) l[j] = i + 1;
				else r[j] = i - 1;
			}
			que[i].clear();
		}
	}
//	reverse(p + 1, p + m + 1);
//	for(int i = 1; i <= m; ++i) cout <<  p[i].second << " " << p[i].first << "\n";
	for(int i = 1; i <= q; ++i){
		que[r[i]].push_back(i);
//		cout << l[i] << " "<< r[i] << "\n";
	}
	build();
//	for(int i = m; i >= 1; --i) update(in[e2[p[i].second]], 1), update(out[e2[p[i].second]], -1);
	for(int i = m; i >= 0; --i){
		for(ll j : que[i]){
			ll s = get(in[a[j]]) + get(in[b[j]]) - 2 * get(in[lc[j]]);
//			cout << i << " " << j << " " << get(in[a[j]]) << " " << get(in[b[j]]) << " " << get(in[lc[j]]) << " " << c[j] << "\n";
			if(s <= c[j]) ans[j] = c[j] - s;
			else ans[j] = -1;
		}
		if(i > 0)update(in[e2[p[i].second]], 1), update(out[e2[p[i].second]], -1);
//		, cout << i << " "<< e2[p[i].second] << "\n";
	}
	for(int i = 1; i <= q; ++i) cout << ans[i] << "\n";
    return;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	if(fopen(".INP", "r")) {
		freopen(".INP", "r", stdin);
		freopen(".OUT", "w", stdout);
	}
	int testCase = 1;
	//cin >> testCase;
	while(testCase--) solve();
}

Compilation message (stderr)

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

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