제출 #805185

#제출 시각아이디문제언어결과실행 시간메모리
805185SharkyTwo Currencies (JOI23_currencies)C++17
10 / 100
5074 ms37780 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define sz(x) (int)x.size() const int maxn = 1E5+8; 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, ls[maxn]; void dfs(int u, int pr = -1) { for (auto& [v, c] : adj[u]) { if (v == pr) continue; dfs(v, u); ls[v] = u; } } 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; 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}); } while (q--) { int s, t, x, y; cin >> s >> t >> x >> y; for (int i = 1; i <= n; i++) ls[i] = -1; vector<int> path, c; dfs(s); int bk = t; while (bk != -1) { path.push_back(bk); bk = ls[bk]; } reverse(path.begin(), path.end()); // for (int& e : path) cout << e << " "; // cout << "\n"; for (int i = 0; i < sz(path) - 1; i++) { int l = path[i], r = path[i+1]; for (int& e : edges[mp[{l, r}]].c) c.push_back(e); } sort(c.begin(), c.end()); int cur = 0, mnd = sz(c); for (int i = 0; i < sz(c); i++) { cur += c[i]; if (cur <= y) { int d = sz(c) - i - 1; mnd = min(mnd, d); } } if (x < mnd) { cout << "-1\n"; goto bye; } cout << x - mnd << "\n"; bye:{} } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...