Submission #888627

#	Time	Username	Problem	Language	Result	Execution time	Memory
888627		vjudge1	Two Currencies (JOI23_currencies)	C++17	0 / 100	4 ms	21084 KiB

currencies

/*

author : abushbandit
contest : ---

*/

#include "bits/stdc++.h"

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;

using namespace std;

#define int long long
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define ff first
#define ss second
#define pb push_back
#define rep(i,s,f) for(int i = s;i < f;i++)

#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>

#pragma GCC optimize("Ofast,no-stack-protector,fast-math",3)

template <class type1>
	using ordered_multiset = tree <type1, null_type, less_equal <type1>, rb_tree_tag, tree_order_statistics_node_update>;

typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<pair<int,int>> vii;
typedef pair<int,int> pii;

const ll INF = 1e18;
const ll MOD7 = 1e9 + 7;
const ll MOD9 = 998244353;
const ld PI = acos(-1.0);
const int N = 1e5 + 6;

template <class F, class _S>
bool chmin(F &u, const _S &v){
    bool flag = false;
    if ( u > v ){
        u = v; flag |= true;
    }
    return flag;
}

template <class F, class _S>
bool chmax(F &u, const _S &v){
    bool flag = false;
    if ( u < v ){
        u = v; flag |= true;
    }
    return flag;
    
}

int binpow (int a, int n) {
	int res = 1;
	while (n) {
		if (n & 1)
			res *= a;
		a *= a;
		n >>= 1;
	}
	return res;
}

void start_file(string file){
	freopen((file + ".in").c_str(),"r",stdin);
	freopen((file + ".out").c_str(),"w",stdout);
}

int n, q, timer;
int tin[N], tout[N];
int up[20][N];
vector <pair<int,int>> g[N];
int sz[N];
pair<int,int> par[N];
int cst;

void dfs(int v, int pr,int depth) {
	sz[v] = depth;
    tin[v] = ++timer;
    up[0][v] = pr;
    for (int i = 1; i <= 18; i++) {
        up[i][v] = up[i - 1][ up[i - 1][v] ];
    }
    for (auto [to,cost] : g[v]) {
        if (to == pr) continue;
        dfs(to, v, depth + cost);
    }
    tout[v] = ++timer;
}

bool upper(int a, int b) {
    return tin[a] <= tin[b] && tout[a] >= tout[b];
}

int lca(int a, int b) {
    if (upper(a, b)) return a;
    if (upper(b, a)) return b;
    for (int i = 18; i >= 0; i--) {
        if (!upper(up[i][a], b)) {
            a = up[i][a];
        }
    }
    return up[0][a];
}

void solve(int tc){
	
	int n,m,q;
	cin >> n >> m >> q;
	int a[n],b[n],w[n] {};
	for(int i = 0;i < n - 1;i++){
		cin >> a[i] >> b[i];
		w[i] = 0;
	}
	for(int i = 0;i < m;i++){
		int p,c;
		cin >> p >> c;
		w[p - 1]++;
		cst = c;
	}
	for(int i = 0;i < n - 1;i++){
		g[a[i]].pb({b[i],w[i]});
		g[b[i]].pb({a[i],w[i]});
	}
	dfs(1,1,0);
	for(int i = 0;i < q;i++){
		int s,t,x,y;
		cin >> s >> t >> x >> y;
		int lc = lca(s,t);
		int dis_slc = sz[s] - sz[lc];
		int dis_tlc = sz[t] - sz[lc];
		int sum = dis_slc + dis_tlc;
		sum = sum - (y / cst);
		sum = max(sum,0ll);
		x -= sum;
		if(x <= 0){
			cout << "-1\n";
		} else{
			cout << x << "\n";
		}
	}
	
}

signed main(){

//	start_file("");

	ios_base::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);

	int test_cases = 1;
//	cin >> test_cases ;
	for(int tc = 1;tc <= test_cases;++ tc){
		solve(tc);
	}

}

/*



*/

Compilation message (stderr)

currencies.cpp: In function 'void start_file(std::string)':
currencies.cpp:75:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   75 |  freopen((file + ".in").c_str(),"r",stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
currencies.cpp:76:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |  freopen((file + ".out").c_str(),"w",stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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