제출 #826945

#제출 시각아이디문제언어결과실행 시간메모리
826945khshgTwo Currencies (JOI23_currencies)C++14
28 / 100
310 ms39868 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, pp, cnt; 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]; } void dfs0(int s) { for(auto& v : adj[s]) { int u = v.first; if(u == par[s][0]) continue; cnt[u] = cnt[s] + pp[u]; dfs0(u); } } 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); int c; for(int i = 0; i < M; ++i) { int p; cin >> p >> c; --p; ++pp[e[p].first]; } cnt.resize(N); dfs0(0); while(Q--) { int S, T, X; long long Y; cin >> S >> T >> X >> Y; --S; --T; int L = lca(S, T); int many = max(0LL, cnt[S] + cnt[T] - 2 * cnt[L] - Y / c); int ans = X - many; 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...