Submission #757382

#	Time	Username	Problem	Language	Result	Execution time	Memory
757382		Halym2007	Two Currencies (JOI23_currencies)	C++11	10 / 100	883 ms	17124 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 = 2005;
// 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 n, m, q, l, r;
vector <ll> v[N], vv;
map <ll, bool> mm;
ll kak[N], san[N][N], p[N], c[N], s, t, gold, silver; 
void dfs(int x, int par) {
	kak[x] = par;
	for (auto i : v[x]) {
		if (i != par) {
			dfs (i, x);		
		}
	}
}

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 >> r;
		v[l].pb (r);
		v[r].pb (l);
		san[l][r] = i;
		san[r][l] = i;
		// dan[i].ff = l;
		// dan[i].ss = r;
	}    
	for (int i = 1; i <= m; ++i) {
		cin >> p[i] >> c[i];
	}
	while ( q-- ) {
		cin >> s >> t >> gold >> silver;
		dfs (s, -1);
		mm.clear();
		vv.clear();
		while (kak[t] != -1) {
			mm[san[t][kak[t]]] = 1;
			t = kak[t];
		}
		for (int i = 1; i <= m; ++i) {
			if (mm[p[i]]) {
				vv.pb (c[i]);
			}
		}
		sort (vv.begin(), vv.end());
		for (auto i : vv) {
			if (silver >= i) {
				silver -= i;
			}
			else {
				gold--;
			}
		}
		if (gold < 0) {
			cout << "-1" << endl;
		}
		else cout << gold << endl;
	}
}
/*
██╗░░██╗░█████╗░██╗░░░░░██╗░░░██╗███╗░░░███╗██████╗░░█████╗░░█████╗░███████╗
██║░░██║██╔══██╗██║░░░░░╚██╗░██╔╝████╗░████║╚════██╗██╔══██╗██╔══██╗╚════██║
███████║███████║██║░░░░░░╚████╔╝░██╔████╔██║░░███╔═╝██║░░██║██║░░██║░░░░██╔╝
██╔══██║██╔══██║██║░░░░░░░╚██╔╝░░██║╚██╔╝██║██╔══╝░░██║░░██║██║░░██║░░░██╔╝░
██║░░██║██║░░██║███████╗░░░██║░░░██║░╚═╝░██║███████╗╚█████╔╝╚█████╔╝░░██╔╝░░
╚═╝░░╚═╝╚═╝░░╚═╝╚══════╝░░░╚═╝░░░╚═╝░░░░░╚═╝╚══════╝░╚════╝░░╚════╝░░░╚═╝░░░
*/

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