Submission #885906

#TimeUsernameProblemLanguageResultExecution timeMemory
885906abysmalTwo Currencies (JOI23_currencies)C++14
100 / 100
919 ms41948 KiB
#include<iostream> #include<stdio.h> #include<stdint.h> #include<iomanip> #include<algorithm> #include<utility> #include<vector> #include<stack> #include<queue> #include<set> #include<map> #include<deque> #include<math.h> #include<assert.h> #include<string.h> #include<chrono> #include<bitset> using namespace std; using namespace std::chrono; const int64_t INF = (int64_t) 1e18 + 100; const int64_t mINF = (int64_t) 2 * 1e9 + 5; const int64_t MOD = (int64_t) 20230401; const int64_t MOD2 = 998244353; const int nbit = 63; const int ndig = 10; const int nchar = 26; const int p1 = 31; const int p2 = 53; const int D = 4; int dr[D] = {-1, 0, 1, 0}; int dc[D] = {0, 1, 0, -1}; const int Dk = 8; int drk[Dk] = {2, 2, -2, -2, 1, 1, -1, -1}; int dck[Dk] = {1, -1, 1, -1, 2, -2, 2, -2}; struct Query { int s; int t; int64_t x; int64_t y; Query(int s_, int t_, int64_t x_, int64_t y_) : s(s_), t(t_), x(x_), y(y_) {} }; struct Path { int u; int w; Path(int u_, int w_) : u(u_), w(w_) {} bool operator < (const Path& o) const { return w < o.w; } }; struct Solution { int n; int m; int q; int t; int k; int LOG; vector<int> f; vector<int> pos; vector<int> tin; vector<int> tout; vector<int> depth; vector<Path> path; vector<vector<int> > rmq; vector<vector<int> > adj; Solution() {} void solve() { cin >> n >> m >> q; t = 1; k = 0; f.resize(n); tin.resize(n, 0); tout.resize(n, 0); depth.resize(n, 0); adj.resize(n); vector<pair<int, int> > edges; for(int i = 0; i < n - 1; i++) { int u; int v; cin >> u >> v; u--; v--; edges.emplace_back(u, v); adj[u].push_back(v); adj[v].push_back(u); } DFS(); LOG = 0; while(MASK(LOG) <= k) LOG++; rmq.resize(LOG, vector<int>(k, 0)); for(int i = 0; i < k; i++) { rmq[0][i] = pos[i]; } for(int i = 1; i < LOG; i++) { for(int j = 0; j + MASK(i) - 1 < k; j++) { int d1 = depth[ rmq[i - 1][j] ]; int d2 = depth[ rmq[i - 1][j + MASK(i - 1)] ]; if(d1 < d2) rmq[i][j] = rmq[i - 1][j]; else rmq[i][j] = rmq[i - 1][j + MASK(i - 1)]; } } for(int i = 0; i < m; i++) { int id; int c; cin >> id >> c; id--; int u = edges[id].first; int v = edges[id].second; if(depth[u] > depth[v]) swap(u, v); path.emplace_back(v, c); } sort(path.begin(), path.end()); vector<Query> qury; for(int i = 0; i < q; i++) { int s; int e; int64_t x; int64_t y; cin >> s >> e >> x >> y; s--; e--; qury.emplace_back(s, e, x, y); } vector<int64_t> gold(t + 1, 0); vector<int64_t> silver(t + 1, 0); vector<int> l(q, 0); vector<int> r(q, m); vector<int> ans(q, -1); while(true) { fill(gold.begin(), gold.end(), 0); fill(silver.begin(), silver.end(), 0); for(int i = 0; i < m; i++) { int u = path[i].u; update(tin[u], 1, gold); update(tout[u], -1, gold); } vector<pair<int, int> > mid; for(int i = 0; i < q; i++) { if(l[i] > r[i]) continue; int md = l[i] + (r[i] - l[i]) / 2; mid.emplace_back(md, i); } if((int) mid.size() == 0) break; sort(mid.begin(), mid.end()); int id = 0; for(int i = 0; i < m; i++) { while(id < (int) mid.size() && mid[id].first == i) { int j = mid[id].second; int s = qury[j].s; int e = qury[j].t; int64_t x = qury[j].x; int64_t y = qury[j].y; int lca = LCA(s, e); int64_t sums = sum(tin[s], silver) + sum(tin[e], silver) - 2 * sum(tin[lca], silver); int64_t sumg = sum(tin[s], gold) + sum(tin[e], gold) - 2 * sum(tin[lca], gold); if(x >= sumg && y >= sums) { ans[j] = x - sumg; l[j] = mid[id].first + 1; } else if(x < sumg) l[j] = mid[id].first + 1; else if(y < sums) r[j] = mid[id].first - 1; id++; } int u = path[i].u; int w = path[i].w; update(tin[u], -1, gold); update(tout[u], 1, gold); update(tin[u], w, silver); update(tout[u], -w, silver); } while(id < (int) mid.size()) { int j = mid[id].second; int s = qury[j].s; int e = qury[j].t; int64_t x = qury[j].x; int64_t y = qury[j].y; int lca = LCA(s, e); int64_t sums = sum(tin[s], silver) + sum(tin[e], silver) - 2 * sum(tin[lca], silver); int64_t sumg = sum(tin[s], gold) + sum(tin[e], gold) - 2 * sum(tin[lca], gold); if(x >= sumg && y >= sums) { ans[j] = x - sumg; l[j] = mid[id].first + 1; } else if(x < sumg) l[j] = mid[id].first + 1; else if(y < sums) r[j] = mid[id].first - 1; id++; } } for(int i = 0; i < q; i++) { cout << ans[i] << "\n"; } } int LCA(int i, int j) { i = f[i]; j = f[j]; if(i > j) swap(i, j); int len = j - i + 1; int kk = 31 - __builtin_clz(len); if(depth[ rmq[kk][i] ] < depth[ rmq[kk][j - MASK(kk) + 1] ]) return rmq[kk][i]; return rmq[kk][j - MASK(kk) + 1]; } void DFS(int u = 0, int p = -1) { f[u] = k++; tin[u] = t++; pos.push_back(u); for(int i = 0; i < (int) adj[u].size(); i++) { int v = adj[u][i]; if(v == p) continue; depth[v] = depth[u] + 1; DFS(v, u); pos.push_back(u); k++; } tout[u] = t++; } void update(int i, int64_t val, vector<int64_t>& bit) { while(i < (int) bit.size()) { bit[i] += val; i += i & (-i); } } int64_t sum(int i, vector<int64_t>& bit) { int64_t ans = 0; while(i > 0) { ans += bit[i]; i -= i & (-i); } return ans; } int modadd(int t1, int t2) { int res = t1 + t2; if(res >= MOD) res -= MOD; return res; } int modsub(int t1, int t2) { int res = t1 - t2; if(res < 0) res += MOD; return res; } int modmul(int t1, int t2) { int64_t res = 1LL * t1 * t2; return res % MOD; } int64_t Abs(int64_t t1) { if(t1 < 0) return -t1; return t1; } int64_t MASK(int j) { return (1LL << j); } bool BIT(int64_t t1, int j) { return (t1 & MASK(j)); } }; void __setup() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); // freopen("in.txt", "r", stdin); // freopen("out.txt", "w", stdout); } int main() { __setup(); // auto start = high_resolution_clock::now(); int t = 1; // cin >> t; for(int i = 1; i <= t; i++) { Solution().solve(); } // auto stop = high_resolution_clock::now(); // auto duration = duration_cast<microseconds>(stop - start); // cerr << duration.count() << "\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...