제출 #891978

#제출 시각아이디문제언어결과실행 시간메모리
891978vjudge1Two Currencies (JOI23_currencies)C++17
10 / 100
5056 ms49596 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define ff first #define ss second #define all(a) a.begin(), a.end() const int mod = 998244353; const int N = 1e5; struct Fenwick{ int n; vector<int> fenw; Fenwick(int sz){ n = sz; fenw.resize(n+1, 0); }; void add(int i, int x){ for(; i <= n; i+= i&-i){ fenw[i]+= x; } } int pref(int i){ int s = 0; for(; i > 0; i-= i & -i){ s+= fenw[i]; } return s; } int sum(int l, int r){ return pref(r) - pref(l-1); } }; int n, m, q; vector<int > g[N+10]; vector< pair<int, int> > edge; int depth[N+10], up[N+10][20], sum[N+10][20]; int tin[N+10], tout[N+10], timer = 1; void dfs(int v, int par){ tin[v] = timer++; up[v][0] = par; for(int to : g[v]){ if(to == par) continue; depth[to] = depth[v] + 1; dfs(to, v); } tout[v] = timer - 1; } int lca(int a, int b){ if(depth[b] < depth[a]) swap(a, b); int k = depth[b] - depth[a]; for(int i = 0;i < 20; i++){ if(k & (1<<i)) b = up[b][i]; } if(a == b) return a; for(int i = 19; i >= 0; i--){ if(up[b][i] != up[a][i]){ a = up[a][i]; b = up[b][i]; } } return up[a][0]; } int ones(int a, int d){ int s = 0; for(int i = 0;i < 20; i++){ if(d & (1<<i)){ s+= sum[a][i]; a = up[a][i]; } } return s; } signed main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> m >> q; for(int i = 1;i < n; i++){ int a, b; cin >> a >> b; edge.push_back({a, b}); g[a].push_back(b); g[b].push_back(a); } dfs(1, 1); vector<array<int, 2> > adds; for(int i = 0;i < m; i++){ int p, c; cin >> p >> c; int a = edge[p-1].ff, b = edge[p-1].ss; if(depth[a] < depth[b]) swap(a, b); adds.push_back({a, c}); sum[a][0]+= 1; } sort(all(adds), [&](auto A, auto B){ return A[1] < B[1]; }); for(int j = 1;j < 20; j++){ for(int i = 1;i <= n; i++){ up[i][j] = up[up[i][j-1]][j-1]; sum[i][j] = sum[up[i][j-1]][j-1] + sum[i][j-1]; } } int s, t, x, y, lc; /*vector<array<int, 4> > query; vector<vector<int> > rn(n, vector<int>(2, {0, m+1})); for(auto &A : query){ cin >> A[0] >> A[1] >> A[2] >> A[3]; } * */ auto good=[&](int mid){ Fenwick f1(n + 1), f2(n + 1); int idx = 0; for(auto [a, c] : adds){ f1.add(tin[a], c); f1.add(tout[a] + 1, -c); f2.add(tin[a], 1); f2.add(tout[a] + 1, -1); if(idx == mid) break; idx++; } int sum = f1.pref(tin[s]) + f1.pref(tin[t]) - 2 * f1.pref(tin[lc]); int cnt = f2.pref(tin[s]) + f2.pref(tin[t]) - 2 * f2.pref(tin[lc]); return make_pair(sum, cnt); }; while(q--){ cin >> s >> t >> x >> y; int l = 0, r = m + 1; lc = lca(s, t); int checkpoints = ones(s, depth[s] -depth[lc]) + ones(t, depth[t] - depth[lc]); // cout << "overall there were : " << checkpoints << "\n"; while(l + 1 < r){ int mid = (l + r)>>1; pair<int, int> ch = good(mid); if(ch.ff <= y) l = mid; else r = mid; } if(good(l).ff > y){ cout << max(-1LL, x - checkpoints) << '\n'; continue; } pair<int, int> ch = good(l); // cout << ch.ss << " = "; checkpoints-= ch.ss; cout << max(-1LL, x - checkpoints) << '\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...