제출 #826895

#제출 시각아이디문제언어결과실행 시간메모리
826895khshgTwo Currencies (JOI23_currencies)C++14
10 / 100
5058 ms37660 KiB
#include<bits/stdc++.h> using namespace std; #define int long long const int LG = 20; int N, M, Q; vector<pair<int, int>> e; vector<vector<pair<int, int>>> adj; vector<array<int, LG>> par; vector<int> lvl; vector<vector<int>> pp; void dfs(int s) { for(auto& v : adj[s]) { int u = v.first; if(u == par[s][0]) continue; lvl[u] = lvl[s] + 1; par[u][0] = s; for(int i = 1; i < LG; ++i) { par[u][i] = par[par[u][i - 1]][i - 1]; } dfs(u); } } int lca(int s, int t) { if(lvl[t] > lvl[s]) swap(s, t); for(int i = LG - 1; i >= 0; --i) { if(lvl[par[s][i]] >= lvl[t]) { s = par[s][i]; } } if(s == t) return s; for(int i = LG - 1; i >= 0; --i) { if(par[s][i] != par[t][i]) { s = par[s][i]; t = par[t][i]; } } return par[s][0]; } int32_t main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> N >> M >> Q; adj.resize(N); for(int i = 1; i < N; ++i) { int u, v; cin >> u >> v; --u; --v; e.emplace_back(u, v); adj[u].push_back({v, i}); adj[v].push_back({u, i}); } lvl.resize(N); par.resize(N); dfs(0); for(int i = 0; i + 1 < N; ++i) { if(par[e[i].second][0] == e[i].first) { swap(e[i].first, e[i].second); } } pp.resize(N); for(int i = 0; i < M; ++i) { int p, c; cin >> p >> c; --p; pp[e[p].first].push_back(c); } while(Q--) { int S, T, X; long long Y; cin >> S >> T >> X >> Y; --S; --T; int L = lca(S, T); vector<int> cur; while(S != L) { for(auto& u : pp[S]) { cur.push_back(u); } S = par[S][0]; } while(T != L) { for(auto& u : pp[T]) { cur.push_back(u); } T = par[T][0]; } sort(begin(cur), end(cur)); int ans = X; for(int i = 0; i < (int)cur.size(); ++i) { if(Y - cur[i] >= 0) { Y -= cur[i]; } else { ans = X - ((int)cur.size() - i); break; } } if(ans < 0) { cout << "-1\n"; } else { cout << ans << '\n'; } } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...