Submission #1217425

#	Time	Username	Problem	Language	Result	Execution time	Memory
1217425		cowwycow	Two Currencies (JOI23_currencies)	C++20	40 / 100	1059 ms	112496 KiB

currencies

#include <bits/stdc++.h>
using namespace std;
#define name "aaaaaa"
#define endl "\n"
#define fi first
#define se second
using ll = long long;
using db = double;
using ld = long double;
using pii = pair<ll, ll>;
using pll = pair<ll, ll>;
using ppii = pair<ll, pii>;

const ll N = 1e5 + 5, L = 21;


ll lowbit(ll x){
	return x & -x;
}

ll A[N], B[N], B2[N], n;

void upd(ll x, ll v, ll sus) {
    for(ll i = x ; i <= n ; i += lowbit(i)){
    	B[i] += v;
    	B2[i] += sus;
    }
}

pll query(ll x) {
    pll ans = {0, 0};
    for(ll i = x ; i > 0 ; i -= lowbit(i)){
    	ans.fi += B[i];
    	ans.se += B2[i];
    }
    return ans;
}

void update(ll l, ll r, ll v) {
    upd(r + 1, -v, -1); upd(l, v, 1);
}

void init() {
    fill(B, B + n + 1, 0);
    fill(B2, B2 + n + 1, 0);
}

pii edge[N];
vector<ll> e[N];

ll tin[N], tout[N], timer = 0;

void dfs(ll u, ll par){
	tin[u] = ++timer;
	for(ll v : e[u]){
		if(v == par) continue;
		dfs(v, u);
	}
	tout[u] = timer;
}

 
ll par[N][L], dep[N];
 
void dfs2(ll u, ll p){
    dep[u] = dep[p] + 1;
    par[u][0] = p;
    for(ll i = 1; i < L; i++){
        par[u][i] = par[par[u][i - 1]][i - 1];
    }
    for(ll v : e[u]){
        if(v == p) continue;
        dfs2(v, u);
    }
}

ll gold[N];

void dfsgold(ll u, ll par){
	for(ll v : e[u]){
		if(v == par) continue;
		gold[v] += gold[u];
		dfsgold(v, u);
	}
}
 
ll ancestork(ll u, ll dist){
    for(ll i = 0; i < L; i++){
        if(dist >> i & 1) u = par[u][i];
    }
    return u;
}
 
ll lca(ll u, ll v){
    if(dep[u] < dep[v]) swap(u, v);
    u = ancestork(u, dep[u] - dep[v]);
    if(u == v) return u;
    for(ll i = L - 1; i >= 0; i--){
        if(par[v][i] != par[u][i]){
            v = par[v][i];
            u = par[u][i];
        }
    }
    ll l = par[v][0];
    return l;
}

pll distroot(ll x){
	return query(tin[x]);
}

pll path(ll u, ll v){
	pll res = {0, 0};
	pll p1 = distroot(u), p2 = distroot(v), p3 = distroot(lca(u, v));
	res.fi = p1.fi + p2.fi - p3.fi * 2;
	res.se = p1.se + p2.se - p3.se * 2;
	return res;
}


ll goldpath(ll u, ll v){
	return gold[u] + gold[v] - gold[lca(u, v)] * 2;
}

pll p[N];

ll s[N], t[N]; ll x[N], y[N];

struct bs{
	ll l, r, mid, id;
};

bs b[N];
ll sus[N];

vector<bs> midcur[N];

void solve(){
	ll m, q;
	cin >> n >> m >> q;
	for(ll i = 1; i < n; i++){
		ll u, v;
		cin >> u >> v;
		e[u].push_back(v);
		e[v].push_back(u);
		edge[i] = {u, v};
	}

	for(ll i = 1; i <= m; i++){
		cin >> p[i].se >> p[i].fi;
	}
	sort(p + 1, p + m + 1);

	dfs(1, -1);
	dfs2(1, -1);

	for(ll i = 1; i < n; i++){
		ll u = edge[i].fi, v = edge[i].se;
		if(tin[u] > tin[v]) swap(edge[i].fi, edge[i].se);
	}

	for(ll i = 1; i <= m; i++){
		gold[edge[p[i].se].se]++;
	}

	dfsgold(1, -1);

	for(ll i = 1; i <= q; i++){
		cin >> s[i] >> t[i] >> x[i] >> y[i];
		b[i] = {0, m, 1, i};
	}

	for(ll z = 1; z < L; z++){
		init();
		for(ll i = 0; i <= m; i++){
			midcur[i].clear();
		}
		for(ll i = 1; i <= q; i++){
			b[i].mid = (b[i].l + b[i].r + 1) / 2;
			midcur[b[i].mid].push_back(b[i]);
		}
		for(ll i = 1; i <= m; i++){
			ll id = p[i].se;
			ll u = edge[id].fi, v = edge[id].se;
			update(tin[v], tout[v], p[i].fi);
			for(auto [l, r, mid, id] : midcur[i]){
				if(l == r) continue;
				u = s[id], v = t[id];
				pll cur = path(u, v);
				if(cur.fi <= y[id]){
					b[id].l = mid;
					sus[id] = cur.se;
				}else{
					b[id].r = mid - 1;
				}
			}
		}
	}

	for(ll i = 1; i <= q; i++){
		ll g = goldpath(s[i], t[i]);
		ll silver_used = sus[i];
		ll gold_used = g - silver_used;
		if(gold_used > x[i]){
			cout << -1 << endl;
		}else{
			cout << x[i] - gold_used << endl;
		}
	}
}


int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	if(fopen(name".inp", "r")) {
		freopen(name".inp", "r", stdin);
		freopen(name".out", "w", stdout);
	}
	ll test = 1;
	//cin >> test;
	while(test--){
		solve();
	}
}

Compilation message (stderr)

currencies.cpp: In function 'int main()':
currencies.cpp:216:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  216 |                 freopen(name".inp", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
currencies.cpp:217:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  217 |                 freopen(name".out", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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