oj.uz

Submission #757367

# Submission time Handle Problem Language Result Execution time Memory
757367 2023-06-13T06:24:45 Z Halym2007 Two Currencies (JOI23_currencies) C++11
0 / 100
 438 ms 11044 KB 
#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;}
int n, m, q;
int l, r;
vector <int> v[N], vv;
map <int, bool> mm;
int 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) {
			// kak[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;
		for (int i = 1; i <= n; ++i) {
			kak[i] = -1;
		}
		dfs (s, -1);
		// return 0;
		// for (int i = 1; i <= n; ++i) {
		// 	cout << kak[i] << "\n";
		// }
		// return 0;
		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) {
		// 	cout << i << " ";
		// }
		// return 0;
		for (auto i : vv) {
			if (silver >= i) {
				silver -= i;
			}
			else {
				gold--;
			}
		}
		if (gold < 0) {
			cout << "-1" << endl;
		}
		else cout << gold << endl;
	}
}
/*
██╗░░██╗░█████╗░██╗░░░░░██╗░░░██╗███╗░░░███╗██████╗░░█████╗░░█████╗░███████╗
██║░░██║██╔══██╗██║░░░░░╚██╗░██╔╝████╗░████║╚════██╗██╔══██╗██╔══██╗╚════██║
███████║███████║██║░░░░░░╚████╔╝░██╔████╔██║░░███╔═╝██║░░██║██║░░██║░░░░██╔╝
██╔══██║██╔══██║██║░░░░░░░╚██╔╝░░██║╚██╔╝██║██╔══╝░░██║░░██║██║░░██║░░░██╔╝░
██║░░██║██║░░██║███████╗░░░██║░░░██║░╚═╝░██║███████╗╚█████╔╝╚█████╔╝░░██╔╝░░
╚═╝░░╚═╝╚═╝░░╚═╝╚══════╝░░░╚═╝░░░╚═╝░░░░░╚═╝╚══════╝░╚════╝░░╚════╝░░░╚═╝░░░
*/

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Incorrect 235 ms 10256 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Incorrect 438 ms 11044 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Incorrect 410 ms 8664 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Incorrect 235 ms 10256 KB Output isn't correct
6 Halted 0 ms 0 KB -