Submission #805210

#TimeUsernameProblemLanguageResultExecution timeMemory
805210SharkyTwo Currencies (JOI23_currencies)C++17
28 / 100
314 ms63496 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define sz(x) (int)x.size() const int maxn = 1E5+8; const int lgn = 18; vector<pair<int, vector<int>>> adj[maxn]; struct edge { int u, v; vector<int> c; }; vector<edge> edges; map<pair<int, int>, int> mp; int n, m, q, C, ls[maxn], dep[maxn], di[maxn], lift[maxn][lgn]; void dfs(int u, int pr = -1) { for (auto& [v, c] : adj[u]) { if (v == pr) continue; dfs(v, u); ls[v] = u; } } void dfs_pre(int u, int pr = -1) { for (int i = 1; i < lgn; i++) lift[u][i] = lift[lift[u][i-1]][i-1]; for (auto& [v, c] : adj[u]) { if (v == pr) continue; dep[v] = dep[u] + 1; di[v] = di[u] + sz(c); lift[v][0] = u; dfs_pre(v, u); } } int jump(int s, int dist) { for (int i = lgn - 1; i >= 0; i--) { if (dist & (1 << i)) s = lift[s][i]; } return s; } int getlca(int u, int v) { if (dep[u] < dep[v]) swap(u, v); u = jump(u, dep[u] - dep[v]); if (u == v) return u; for (int i = lgn - 1; i >= 0; i--) { int ut = lift[u][i], vt = lift[v][i]; if (ut != vt) u = ut, v = vt; } return lift[u][0]; } int32_t main() { ios::sync_with_stdio(0); cin.tie(0); cin >> n >> m >> q; for (int i = 0; i < n - 1; i++) { int u, v; cin >> u >> v; edges.push_back((edge) {u, v, {}}); mp[{u, v}] = mp[{v, u}] = i; } for (int i = 1; i <= m; i++) { int p, c; cin >> p >> c; C = c; edges[p-1].c.push_back(c); } for (auto& [u, v, c] : edges) { adj[u].push_back({v, c}); adj[v].push_back({u, c}); } lift[1][0] = 1; dfs_pre(1); while (q--) { int s, t, x, y; cin >> s >> t >> x >> y; int lca = getlca(s, t); int cnt = di[s] + di[t] - 2 * di[lca]; cnt -= (y / C); if (cnt < 0) cnt = 0; if (x - cnt < 0) cout << "-1\n"; else cout << x - cnt << "\n"; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...