Submission #775021

#	Time	Username	Problem	Language	Result	Execution time	Memory
775021		Halym2007	Two Currencies (JOI23_currencies)	C++11	0 / 100	4 ms	5024 KiB

currencies

#include <bits/stdc++.h>
#define ff first
#define ss second
#define sz size()
#define pb push_back
using namespace std;
typedef long long ll;
const int N = 200005;
const int LOG = 17;
// const int mod = 1e9+7;
// ll bigmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll lvl[N], p[N][LOG], P[N][LOG];
ll gold, silver, val, s, t;
ll n, m, q, l[N], r[N], pol[N];
vector <pair <ll, ll>> adj[N];
void dfs (ll x, ll par) {
	for (pair <ll, ll> i : adj[x]) {
		if (i.ff != par) {
			lvl[i.ff] = lvl[x] + 1;
			p[i.ff][0] = x;
			P[i.ff][0] = i.ss;
			dfs (i.ff, x);
		}
 	}
}

ll kth_ancestor (ll x, ll k) {
	for (ll i = LOG - 1; i >= 0; i--) {
		if (k>>i&1) {
			x = p[x][i];
		}
	}
	return x;
}



ll LCA(ll x, ll y) {
	if (lvl[x] > lvl[y]) {
		x = kth_ancestor(x, lvl[x] - lvl[y]);
	}
	else if (lvl[x] < lvl[y]) {
		y = kth_ancestor(y, lvl[y] - lvl[x]);
	}
	if (x == y) return x;
	for (int i = LOG - 1; i >= 0; i--) {
		if (p[x][i] != p[y][i]) {
			x = p[x][i];
			y = p[y][i];
		}
	} 
	return p[x][0];
}



ll jogap (ll x, ll k) {
	ll ret = 0;
	for (ll i = LOG - 1; i >= 0; i--) {
		if (k>>i&1) {
			ret += P[x][i];
			x = p[x][i];
		}
	}
	return ret;
}


int main() {
	ios::sync_with_stdio(false);
 	cin.tie(0), cout.tie(0);
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    //  clock_t tStart = clock();
    // printf("Time taken: %.2fs\n", (double)(clock() - tStart)/CLOCKS_PER_SEC);
    cin >> n >> m >> q;
    for (int i = 1; i < n; ++i) {
    	cin >> l[i] >> r[i];
    }
    int x, y;
    for (int i = 1; i <= m; ++i) {
    	cin >> x >> y;
   		pol[x]++;
   		val = y;
    }
    for (int i = 1; i < n; ++i) {
    	adj[l[i]].pb ({r[i], pol[i]});
    	adj[r[i]].pb ({l[i], pol[i]});
    }
    dfs (1, 0);
    for (int i = 1; i < LOG; ++i) {
    	for (int j = 1; j <= n; ++j) {
    		if (p[j][i - 1]) {
    			p[j][i] = p[p[j][i - 1]][i - 1];
    			P[j][i] = P[j][i - 1] + P[p[j][i - 1]][i - 1]; 
    		}
    	}
    }
    while ( q-- ) {
    	cin >> s >> t >> gold >> silver;
    	int a1 = LCA(s, t);
    	ll a2 = jogap (s, lvl[s] - lvl[a1]);
    	ll a3 = jogap (t, lvl[t] - lvl[a1]);
    	ll a4 = a2 + a3;
    	a4 -= (silver / val);
    	gold -= a4;
    	if (gold < 0) {
    		cout << "-1\n";
		}
		else cout << gold << "\n";
    }
}
/*
██╗░░██╗░█████╗░██╗░░░░░██╗░░░██╗███╗░░░███╗██████╗░░█████╗░░█████╗░███████╗
██║░░██║██╔══██╗██║░░░░░╚██╗░██╔╝████╗░████║╚════██╗██╔══██╗██╔══██╗╚════██║
███████║███████║██║░░░░░░╚████╔╝░██╔████╔██║░░███╔═╝██║░░██║██║░░██║░░░░██╔╝
██╔══██║██╔══██║██║░░░░░░░╚██╔╝░░██║╚██╔╝██║██╔══╝░░██║░░██║██║░░██║░░░██╔╝░
██║░░██║██║░░██║███████╗░░░██║░░░██║░╚═╝░██║███████╗╚█████╔╝╚█████╔╝░░██╔╝░░
╚═╝░░╚═╝╚═╝░░╚═╝╚══════╝░░░╚═╝░░░╚═╝░░░░░╚═╝╚══════╝░╚════╝░░╚════╝░░░╚═╝░░░
*/

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