Submission #1261990

#	Time	Username	Problem	Language	Result	Execution time	Memory
1261990		tminh	Two Currencies (JOI23_currencies)	C++20	100 / 100	554 ms	99144 KiB

currencies

#include "bits/stdc++.h"
using namespace std;

#define task ""
#define ll long long
#define endl '\n'
#define fi first
#define se second
#define vall(a) (a).begin(), (a).end()
#define sze(a) (int)a.size()
#define pii pair<int, int>
#define pll pair<ll, ll>


#define ep emplace_back
#define pb push_back
#define pf push_front


const ll mod = 1e9 + 7;
const int N = 2e5 + 5;
const ll oo = 1e18;

bool START;

int n, q, m;
pii s[N << 1][20];

int T[N], st[N], en[N], rd[N], h[N];
vector<pii> adj[N];

int cur = 0, t = 0;
void dfs(int u, int p) {
	T[u] = ++cur;
	st[u] = ++t;
	
	s[cur][0] = make_pair(h[u], u);
	for (auto[v, id] : adj[u]) {
		if (v == p) continue;
		rd[id] = v;
		h[v] = h[u] + 1;
		dfs(v, u);

		s[++cur][0] = make_pair(h[u], u);
	}
	en[u] = ++t;
}

int lg[N << 1];
void build() {
	dfs(1, 0);
	for (int i = 2; i <= cur; ++i) lg[i] = lg[i >> 1] + 1;
	for (int i = 1; (1 << i) <= cur; ++i) {
		for (int j = 1; j + (1 << i) - 1 <= cur; ++j) s[j][i] = min(s[j][i - 1], s[j + (1 << (i - 1))][i - 1]);
	}
}
int lca(int u, int v) {
	if (T[u] < T[v]) swap(u, v);
	int k = lg[T[u] - T[v] + 1];
	return min(s[T[u] - (1 << k) + 1][k], s[T[v]][k]).se;
}

struct queries {
	int u, v, x;
	ll y;
	int id;
	queries(int u_, int v_, int x_, ll y_, int id_) : u(u_), v(v_), x(x_), y(y_), id(id_) {}
};
vector<queries> Q;


struct BIT {
	ll bit[N << 1];
	void add(int idx, ll delta) {
		for (; idx <= t; idx += idx & -idx) bit[idx] += delta;
	}
	ll get(int idx) {
		ll ans = 0;
		for (; idx > 0; idx -= idx & -idx) ans += bit[idx];
		return ans;
	}
	ll get(int l, int r) {
		return get(r) - get(l - 1);
	}
} bit;

ll get(int u, int v) {
	int lck = lca(u, v);
	return bit.get(st[u]) + bit.get(st[v]) - (bit.get(st[lck]) << 1);
}


vector<queries> pos[N];
pair<int, ll> e[N];

void dnc(int l, int r, vector<queries> curq) {
	if (l == r) {
		for (queries qq : curq) pos[l].pb(qq);
		return;
	}
	int mid = (l + r) >> 1;
	for (int i = mid; i >= l; --i) {
		bit.add(st[rd[e[i].fi]], e[i].se);
		bit.add(en[rd[e[i].fi]], -e[i].se);
	}
	
	vector<queries> ql, qr;
	for (auto[u, v, x, y, id] : curq) {
		ll cost = get(u, v);
		if (cost > y) {
			ql.pb(queries(u, v, x, y, id));
		} else {
			qr.pb(queries(u, v, x, y - cost, id));
		}
	}
	
	for (int i = mid; i >= l; --i) {
		bit.add(st[rd[e[i].fi]], -e[i].se);
		bit.add(en[rd[e[i].fi]], e[i].se);
	}
	curq.clear();
	dnc(l, mid, ql);
	dnc(mid + 1, r, qr);
}


bool cmp(pii x, pii y) {
	return x.se < y.se;
}

int ans[N];
inline void solve() {
	build();
	sort(e + 1, e + 1 + m, cmp);
	dnc(1, m + 1, Q);

	memset(bit.bit, 0, sizeof(bit.bit));
	for (int i = 1; i <= q; ++i) ans[i] = -1;
	for (auto[u, v, x, y, id] : pos[m + 1]) if (get(u, v) <= x) ans[id] = x - get(u, v);
	for (int i = m; i >= 1; --i) {
		bit.add(st[rd[e[i].fi]], 1);
		bit.add(en[rd[e[i].fi]], -1);
		for (auto[u, v, x, y, id] : pos[i]) if (get(u, v) <= x) ans[id] = x - get(u, v);
		
	}
	for (int i = 1; i <= q; ++i) cout << ans[i] << endl;
}


inline void input() {
    cin >> n >> m >> q;
    for (int i = 1; i < n; ++i) {
    	int u, v;
    	cin >> u >> v;
    	adj[u].pb(make_pair(v, i));
    	adj[v].pb(make_pair(u, i));
    }
    for (int i = 1; i <= m; ++i) cin >> e[i].fi >> e[i].se;
    for (int i = 1; i <= q; ++i) {
    	int u, v, x;
    	ll y;
    	cin >> u >> v >> x >> y;
    	Q.pb(queries(u, v, x, y, i));
    	
    }
    return solve();
}
bool END;

int main() {
    if(fopen(task ".inp", "r")) {
        freopen(task ".inp", "r", stdin);
        freopen(task ".out", "w", stdout);
    }
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    input();
    
    
    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << 's' << endl;
    cerr << "Memory: " << fabs ((&END - &START)) / 1048576.0 << "MB\n";
    return 0;
}

Compilation message (stderr)

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

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