제출 #1281873

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1281873		muhammad-ahmad	Two Currencies (JOI23_currencies)	C++20	28 / 100	141 ms	36292 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];
}

void solve() {
	int n, m, q; cin >> n >> m >> q;
	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: 0 / 10
• Subtask 2: 28 / 28
• Subtask 3: 0 / 30
• Subtask 4: 0 / 32