Submission #830664

#TimeUsernameProblemLanguageResultExecution timeMemory
830664enerelt14Two Currencies (JOI23_currencies)C++14
0 / 100
9 ms8748 KiB
#include <algorithm> #include <array> #include <bitset> #include <cassert> #include <chrono> #include <climits> #include <cmath> #include <complex> #include <cstring> #include <functional> #include <iomanip> #include <iostream> #include <map> #include <numeric> #include <queue> #include <random> #include <set> #include <vector> using namespace std; #define ll long long #define ff first #define ss second #define pb push_back const int MX = 1e5 + 5; const int mod = 998244353; int n, m, q; int a[MX], b[MX]; int p[MX], c[MX]; int s[MX], t[MX], x[MX], y[MX]; int l[MX], r[MX], mid[MX], ans[MX]; int pos[MX], sz[MX], d[MX]; int hld_pa[MX], pa[MX]; ll tree[4 * MX], nm[4 * MX]; int cnt, num; vector<int> adj[MX], h[MX]; vector<pair<int, int>> cst; void dfs(int u, int pre) { pa[u] = pre; sz[u] = 1; int mx = 0; for(int i = 0; i < (int)adj[u].size(); i++) { if(adj[u][i] == pre) continue; d[adj[u][i]] = d[u] + 1; dfs(adj[u][i], u); mx = max(mx, sz[adj[u][i]]); sz[u] += sz[adj[u][i]]; } for(int i = 0; i < (int)adj[u].size(); i++) { if(adj[u][i] == pre) continue; if(sz[adj[u][i]] == mx) { swap(adj[u][i], adj[u][0]); break; } } } void hld(int u) { pos[u] = num; num++; for(int i = 0; i < (int)adj[u].size(); i++) { if(d[adj[u][i]] < d[u]) continue; if(!i) hld_pa[adj[u][i]] = hld_pa[u]; else hld_pa[adj[u][i]] = adj[u][i]; } for(int i = 0; i < (int)adj[u].size(); i++) { if(d[adj[u][i]] < d[u]) continue; hld(adj[u][i]); } } void update(int id, int l, int r, int pos, int x) { tree[id] += x; nm[id]++; if(l == r) return; int mid = (l + r) / 2; if(mid < pos) update(id * 2 + 2, mid + 1, r, pos, x); else update(id * 2 + 1, l, mid, pos, x); } ll query(int id, int l, int r, int L, int R) { if(L > r || l > R) return 0; if(L <= l && r <= R) return tree[id]; int mid = (l + r) / 2; return query(id * 2 + 1, l, mid, L, R) + query(id * 2 + 2, mid + 1, r, L, R); } int ch_p(int id, int l, int r, int L, int R) { if(L > r || l > R) return 0; if(L <= l && r <= R) return nm[id]; int mid = (l + r) / 2; return ch_p(id * 2 + 1, l, mid, L, R) + ch_p(id * 2 + 2, mid + 1, r, L, R); } bool is; ll find(int u, int v) { if(hld_pa[u] == hld_pa[v]) { if(u == v) return 0; if(d[u] < d[v]) return query(0, 0, n - 1, pos[u] + 1, pos[v]); else return query(0, 0, n - 1, pos[v] + 1, pos[u]); } if(d[hld_pa[u]] < d[hld_pa[v]]) return find(u, pa[hld_pa[v]]) + query(0, 0, n - 1, pos[hld_pa[v]], pos[v]); else return find(pa[hld_pa[u]], v) + query(0, 0, n - 1, pos[hld_pa[u]], pos[u]); } int cnt_ch_p(int u, int v) { if(hld_pa[u] == hld_pa[v]) { if(u == v) return 0; if(d[u] < d[v]) return ch_p(0, 0, n - 1, pos[u] + 1, pos[v]); else return ch_p(0, 0, n - 1, pos[v] + 1, pos[u]); } if(d[hld_pa[u]] < d[hld_pa[v]]) return cnt_ch_p(u, pa[hld_pa[v]]) + ch_p(0, 0, n - 1, pos[hld_pa[v]], pos[v]); else return cnt_ch_p(pa[hld_pa[u]], v) + ch_p(0, 0, n - 1, pos[hld_pa[u]], pos[u]); } void go() { memset(tree, 0, sizeof(tree)); for(int i = 0; i < m; i++) { update(0, 0, n - 1, pos[cst[i].ss], cst[i].ff); for(int j = 0; j < (int)h[i].size(); j++) { if(i == 1 && h[i][j] == 0) is = 1; ll z = find(s[h[i][j]], t[h[i][j]]); if(i == 1 && h[i][j] == 0) is = 0; if(z > y[h[i][j]]) { if(l[h[i][j]] == r[h[i][j]]) { ans[h[i][j]] = i - 1; cnt++; } else { r[h[i][j]] = mid[h[i][j]]; mid[h[i][j]] = (r[h[i][j]] + l[h[i][j]]) / 2; } } else { if(l[h[i][j]] == r[h[i][j]]) { ans[h[i][j]] = i; cnt++; } else { l[h[i][j]] = mid[h[i][j]] + 1; mid[h[i][j]] = (r[h[i][j]] + l[h[i][j]]) / 2; } } } h[i].clear(); } for(int i = 0; i < q; i++) { if(ans[i]) continue; h[mid[i]].pb(i); } } void solve() { for(int i = 0; i < q; i++) { if(ans[i] >= 0) h[ans[i]].pb(i); } for(int i = 0; i < m; i++) { update(0, 0, n - 1, pos[cst[i].ss], cst[i].ff); for(int j = 0; j < (int)h[i].size(); j++) { ans[h[i][j]] = cnt_ch_p(s[h[i][j]], t[h[i][j]]); } } for(int i = 0; i < q; i++) { ans[i] = cnt_ch_p(s[i], t[i]) - ans[i]; if(ans[i] > x[i]) ans[i] = -1; else ans[i] = x[i] - ans[i]; } } int main() { ios::sync_with_stdio(0);cin.tie(0); cin >> n >> m >> q; for(int i = 0; i < n - 1; i++) { cin >> a[i] >> b[i]; a[i]--; b[i]--; adj[a[i]].pb(b[i]); adj[b[i]].pb(a[i]); } dfs(0, 0); hld(0); for(int i = 0; i < m; i++) { cin >> p[i] >> c[i]; p[i]--; if(d[a[p[i]]] > d[b[p[i]]]) cst.pb({c[i], a[p[i]]}); else cst.pb({c[i], b[p[i]]}); } sort(cst.begin(), cst.end()); for(int i = 0; i < q; i++) { cin >> s[i] >> t[i] >> x[i] >> y[i]; s[i]--; t[i]--; l[i] = 0; r[i] = m - 1; mid[i] = r[i] / 2; h[mid[i]].pb(i); } while(cnt < q) { go(); } solve(); for(int i = 0; i < q; i++) cout << ans[i] << "\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...