Submission #1281899

#	Time	Username	Problem	Language	Result	Execution time	Memory
1281899		muhammad-ahmad	Two Currencies (JOI23_currencies)	C++20	38 / 100	246 ms	36336 KiB

currencies

// #pragma GCC target ("avx2")
// #pragma GCC optimize ("O3")
// #pragma GCC optimize ("unroll-loops")

// #include <bits/stdc++.h>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <map>
#include <vector>
#include <iomanip>
#include <string>
#include <queue>
#include <set>
#include <deque>
#include <numeric>
#include <stack>
using namespace std;

#define int long long
#define endl "\n"

const int N = 1e5 + 5;
const int L = 18;
vector<pair<int, int>> adj[N];
int dist1[N], dist2[N], par[N], sp[N][L];

void sp_table(int u){
	sp[u][0] = par[u];
	int power = 1;
	for (int i = 1; i < L; i++){
		power *= 2;
		if (dist1[u] < power) sp[u][i] = 0;
		else sp[u][i] = sp[sp[u][i - 1]][i - 1];
	}
}
 
void dfs(int u){
	sp_table(u);
	for (auto [i, w] : adj[u]){
		if (par[u] != i){
			dist2[i] = dist2[u] + w;
			dist1[i] = dist1[u] + 1;
			par[i] = u;
			dfs(i);
		}
	}
}

int kth_ancestor(int u, int k){
	if (k == 0) return u;
	int power = 1;
	int ans = u;
	for (int i = 0; i < L; i++){
		if (k & power){
			ans = sp[ans][i]; 
		}
		power *= 2;
	}
	return ans;
}

int LCA(int u, int v){
	if (dist1[u] > dist1[v]) swap(u, v);
	v = kth_ancestor(v, dist1[v] - dist1[u]);
	int power = 1;
	for (int i = 1; i < L; i++) power *= 2;
	if (u == v) return u;
	for (int i = L - 1; i >= 0; i--){
		if (sp[u][i] != sp[v][i]){
			u = sp[u][i];
			v = sp[v][i];
		}
		power /= 2;
	}
	return par[v];
}

const int N1 = 2e3 + 5;
vector<int> adj1[N1];
map<pair<int, int>, int> edge1;
vector<int> E1[N1];
int par1[N1];

void dfs1(int u, int p){
	par1[u] = p;
	for (auto v : adj1[u]){
		if (v == p) continue;
		dfs1(v, u);
	}
	
}

void solve() {
	int n, m, q; cin >> n >> m >> q;
	if (n <= 2000 && m <= 2000 && q <= 2000){
		for (int i = 1; i < n; i++){
		int u, v; cin >> u >> v;
		edge1[{u, v}] = i;
		edge1[{v, u}] = i;
		adj1[u].push_back(v);
		adj1[v].push_back(u);
		}
		
		for (int i = 1; i <= m; i++){
		int p1, c1; cin >> p1 >> c1;
		E1[p1].push_back(c1);
		}
		
		for (int Q = 1; Q <= q; Q++){
		int u, v, g, s;
		cin >> u >> v >> g >> s;
		dfs1(u, 0);
		int x = v;
		vector<int> cost1;
		while (x != u){
			for (auto j : E1[edge1[{x, par1[x]}]]) cost1.push_back(j);
			x = par1[x];
		}
		sort(cost1.begin(), cost1.end());
		int use = cost1.size();
		for (auto i : cost1){
			if (s - i >= 0){
				s -= i;
				use--;
			}
		}
		if (use > g) cout << -1 << endl;
		else cout << g - use << endl;
	}
		return;
	}
	vector<vector<int>> x;
	for (int i = 1; i < n; i++){
		int u, v; cin >> u >> v;
		x.push_back({u, v, 0});
	}
	
	int C;
	
	for (int i = 1; i <= m; i++){
		int p; cin >> p >> C;
		x[p - 1][2]++;
	}
	
	for (auto i : x){
		adj[i[0]].push_back({i[1], i[2]});
		adj[i[1]].push_back({i[0], i[2]});
	}
	
	dfs(1);
	
	for (int i = 1; i <= q; i++){
		int u, v, g, s;
		cin >> u >> v >> g >> s;
		int d1 = s / C;
		// cout << d1 << endl;
		int D1 = dist1[u] + dist1[v] - 2 * dist1[LCA(u, v)];
		int D2 = dist2[u] + dist2[v] - 2 * dist2[LCA(u, v)];
		D2 -= d1;
		if (D2 > g) cout << -1 << endl;
		else cout << g - max(0ll, D2) << endl;
	}
	
    return;
}

signed main() {
    // freopen("", "r", stdin);
    // freopen("", "w", stdout);	
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cout << setprecision(9);
    srand(time(0));

    int tc = 1;
    // cin >> tc;
    while (tc--) {
        solve();
    }
    return 0;
}

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