Submission #1217547

#TimeUsernameProblemLanguageResultExecution timeMemory
1217547thdh__Two Currencies (JOI23_currencies)C++20
100 / 100
1327 ms65176 KiB
#include <bits/stdc++.h> #define ll long long #define pb push_back #define eb emplace_back #define pu push #define ins insert #define fi first #define se second #define all(a) a.begin(),a.end() #define bruh ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0); #define fu(x,a,b) for (auto x=a;x<=b;x++) #define fd(x,a,b) for (auto x=a;x>=b;x--) #define int ll using namespace std; #pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") //mt19937 mt(chrono::steady_clock::now().time_since_epoch().count()); /* Competitive Programming notes that I need to study & fix my dumbass self: 1. Coding: - Always be sure to check the memory of arrays (maybe use vectors), for loops, I don't know - Always try to maximize the memory if possible, even if you are going for subtasks - Do not exploit #define int long long, it will kill you 2. Stress: - Don't be cocky and think stressing with your dumbass brute-force solution will give you guaranteed AC. - Always try generating big testcases and try if they run 3. Time management: - Don't overcommit or undercommit, always spend a certain amount of time to think a problem, don't just look at it and say I'm fucked - Do not spend too much time coding brute-force solutions, they should be easily-codable solutions that don't take up too much time I hate offline because I am dumb */ typedef pair<int, int> ii; const int N = 1e5+5; const int M = 17; const int mod = 1e9+7; const int inf = 1e18; using cd = complex<double>; const long double PI = acos(-1); int power(int a,int b) {ll x = 1;if (a >= mod) a%=mod; while (b) {if (b & 1) x = x*a % mod;a = a*a % mod;b>>=1;}return x;} // Fenwick int bit[N]; void upd(int i, int v) { for (; i < N; i += i & -i) bit[i] += v; } int get(int i) { int ret = 0; for (; i; i -= i & -i) ret += bit[i]; return ret; } int query(int l, int r) { return get(r) - get(l-1); } int n,m,q; vector<int> adj[N], cand[N]; vector<ii> c, e; int s[N], t[N], x[N], y[N], l[N], r[N], mid[N], cost[N]; // HLD + binlift int sz[N], h[N], par[N], tin[N], tout[N], heavy[N], head[N], up[N][M], tot[N]; int timer = 0; void predfs(int u, int p) { sz[u] = 1; up[u][0] = par[u] = p; for (int i = 1; i < M; i++) up[u][i] = up[up[u][i-1]][i-1]; for (auto v : adj[u]) { if (v == p) continue; h[v] = h[u] + 1; predfs(v,u); sz[u] += sz[v]; if (sz[heavy[u]] < sz[v]) heavy[u] = v; } } void decompose(int u, int p) { tin[u] = ++timer, head[u] = p; if (heavy[u]) { decompose(heavy[u], p); } for (auto v : adj[u]) { if (v == par[u] || v == heavy[u]) continue; decompose(v,v); } tout[u] = timer; } int lca(int u,int v) { if (h[u] < h[v]) swap(u,v); int diff = h[u]-h[v]; for (int i=0;i<M;i++) { if (diff >> i & 1) u = up[u][i]; } if (u==v) return u; for (int i=M-1;i>=0;i--) { if (up[u][i] != up[v][i]) u = up[u][i], v = up[v][i]; } return up[u][0]; } int sumpath(int a, int b) { int res = 0; for (; head[a] != head[b]; b = par[head[b]]) { if (h[head[a]] > h[head[b]]) swap(a,b); res += query(tin[head[b]], tin[b]); } if (h[a] > h[b]) swap(a,b); res += query(tin[a], tin[b]); return res - cost[a]; } int dist(int u, int v) { return tot[u] + tot[v] - 2 * tot[lca(u,v)]; } void dfscost(int u, int p) { for (auto v : adj[u]) { if (v == p) continue; tot[v] = tot[u] + cost[v]; dfscost(v,u); } } void solve() { cin>>n>>m>>q; for (int i = 1; i < n; i++) { int u,v; cin>>u>>v; adj[u].pb(v); adj[v].pb(u); e.pb({u,v}); } predfs(1,1); decompose(1,1); c.pb({0,0}); for (int i = 0; i < m; i++) { int p, cc; cin>>p>>cc; --p; int u = e[p].fi, v = e[p].se; if (h[u] < h[v]) c.pb({cc, v}), cost[v]++; else c.pb({cc, u}), cost[u]++; } sort(all(c)); dfscost(1,1); // for (auto i : c) cout<<i.se<<" "<<i.fi<<endl; // cout<<endl; for (int i = 0; i < q; i++) { cin>>s[i]>>t[i]>>x[i]>>y[i]; l[i] = 0, r[i] = m; } while (true) { bool check = 0; for (int i = 0; i < q; i++) { if (l[i] >= r[i]) continue; check = 1; mid[i] = (l[i] + r[i] + 1) >> 1; cand[mid[i]].pb(i); } if (!check) break; // for (int i = 0; i < q; i++) cout<<l[i]<<" "<<r[i]<<endl; for (int i = 1; i <= n; i++) bit[i] = 0, cost[i] = 0; for (int i = 0; i <= m; i++) { // cout<<i<<endl; if (i) { // cout<<c[i].se<<" "<<c[i].fi<<endl; upd(tin[c[i].se], c[i].fi); cost[c[i].se] += c[i].fi; } for (auto j : cand[i]) { int sum = sumpath(s[j], t[j]); // cout<<s[j]<<" "<<t[j]<<" "<<sum<<endl; if (sum <= y[j]) l[j] = mid[j]; else r[j] = mid[j]-1; } // cout<<endl; cand[i].clear(); } // break; } // for (int i = 0; i < q; i++) cout<<l[i]<<" "; // cout<<endl; vector<int> ans(q); for (int i = 0; i < q; i++) cand[l[i]].pb(i); for (int i = 1; i <= n; i++) bit[i] = 0, cost[i] = 0; for (int i = 0; i <= m; i++) { if (i) { // cout<<c[i].se<<" "<<c[i].fi<<endl; upd(tin[c[i].se], 1); cost[c[i].se]++; } for (auto j : cand[i]) { int gold = dist(s[j], t[j]) - sumpath(s[j], t[j]); // cout<<s[j]<<" "<<t[j]<<" "<<dist(s[j], t[j])<<" "<<sumpath(s[j], t[j])<<endl; if (gold > x[j]) ans[j] = -1; else ans[j] = x[j] - gold; } } for (int i = 0; i < q; i++) cout<<ans[i]<<endl; } /* Go through the mistakes you usually make and revise your code, for god's sake... */ signed main() { bruh //freopen("input.inp","r",stdin); //freopen("output.inp","w",stdout); solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...