Submission #832614

#	Time	Username	Problem	Language	Result	Execution time	Memory
832614		beaconmc	Two Currencies (JOI23_currencies)	C++14	28 / 100	563 ms	40876 KiB

currencies

#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

typedef long long ll;
using namespace std;
//using namespace __gnu_pbds;

#define FOR(i, x, y) for(ll i=x; i<y; i++)
#define FORNEG(i, x, y) for(ll i=x; i>y; i--)
//#define ordered_set tree<ll, null_type,less_equal<ll>, rb_tree_tag,tree_order_statistics_node_update>
#define fast() ios_base::sync_with_stdio(false);cin.tie(NULL)

vector<ll> edges[100001];
ll toll[100001];
ll par[100001];
ll depth[100001];
ll pref[100001];
ll ancc[100001][20];

ll fixcost = 0;

vector<vector<ll>> stuff;


void dfs(ll a, ll p, ll d){
	par[a] = p;
	depth[a] = d;
	for (auto&i : edges[a]){
		if (i!=p) dfs(i, a, d+1);
	}
}

void dfs2(ll a, ll p){
	if (p!=-1) pref[a] = pref[p] + toll[a];
	for (auto&i : edges[a]){
		if (i!=p) dfs2(i, a);
	}
}
ll anc(ll a, ll jump){
	if (ancc[a][jump] != -1) return ancc[a][jump];
	if (depth[a] - (1<<jump) <= 0) return 1;
	if (jump == 0) return par[a];

	ancc[a][jump] = anc(anc(a, jump-1), jump-1);
	return ancc[a][jump];
}

ll lca(ll a, ll b){
	if (depth[a] < depth[b]) swap(a,b);
	FORNEG(i,19,-1) if (depth[anc(a, i)] >= depth[b]) a=anc(a,i);
	if (a==b) return a;
	FORNEG(i,19,-1) if (anc(a,i) != anc(b,i)) a = anc(a,i), b = anc(b, i);

	return par[a];
}

int main(){
	FOR(i,0,100001) toll[i] = 0, par[i] = -1, depth[i] = 0, pref[i] = 0;
	FOR(i,0,100001) FOR(j,0,20) ancc[i][j] = -1;

	ll n,m,q;
	cin >> n >> m >> q;
	FOR(i,0,n-1){
		ll a,b;
		cin >> a >> b;
		stuff.push_back({a,b});
		edges[a].push_back(b);
		edges[b].push_back(a);
	}

	dfs(1, -1, 0);

	FOR(i,0,m){
		ll c,d;

		cin >> c >> d;
		ll a = stuff[c-1][0];
		ll b = stuff[c-1][1];

		if (par[b] == a) toll[b] += d;
		else toll[a] += d;

		fixcost = d;
	}

	dfs2(1, -1);

	FOR(i,0,q){
		ll a,b,c,d;
		cin >> a >> b >> c >> d;

		ll total = 0;
		total += pref[a];
		total += pref[b];
		total -= 2*pref[lca(a,b)];
		ll count = total/fixcost;

		count -= (d/fixcost);
		count = max(count, (ll) 0);
		if (c-count < 0 ) cout << -1 << "\n";
		else cout << c-count << "\n";

	}



}

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