Submission #1217417

#TimeUsernameProblemLanguageResultExecution timeMemory
1217417cowwycowTwo Currencies (JOI23_currencies)C++20
40 / 100
837 ms67424 KiB
#include <bits/stdc++.h> using namespace std; #define name "aaaaaa" #define endl "\n" #define fi first #define se second using ll = long long; using db = double; using ld = long double; using pii = pair<int, int>; using pll = pair<ll, ll>; using ppii = pair<int, pii>; const int N = 1e5 + 5, L = 21; int lowbit(int x){ return x & -x; } ll A[N], B[N], B2[N], n; void upd(ll x, ll v, ll sus) { for(ll i = x ; i <= n ; i += lowbit(i)){ B[i] += v; B2[i] += sus; } } pll query(ll x) { pll ans = {0, 0}; for(ll i = x ; i > 0 ; i -= lowbit(i)){ ans.fi += B[i]; ans.se += B2[i]; } return ans; } void update(ll l, ll r, ll v) { upd(r + 1, -v, -1); upd(l, v, 1); } void init() { fill(B, B + n + 1, 0); fill(B2, B2 + n + 1, 0); } pii edge[N]; vector<int> e[N]; int tin[N], tout[N], timer = 0; void dfs(int u, int par){ tin[u] = ++timer; for(int v : e[u]){ if(v == par) continue; dfs(v, u); } tout[u] = timer; } int par[N][L], dep[N]; void dfs2(int u, int p){ dep[u] = dep[p] + 1; par[u][0] = p; for(int i = 1; i < L; i++){ par[u][i] = par[par[u][i - 1]][i - 1]; } for(int v : e[u]){ if(v == p) continue; dfs2(v, u); } } int gold[N]; void dfsgold(int u, int par){ for(int v : e[u]){ if(v == par) continue; gold[v] += gold[u]; dfsgold(v, u); } } int ancestork(int u, int dist){ for(int i = 0; i < L; i++){ if(dist >> i & 1) u = par[u][i]; } return u; } int lca(int u, int v){ if(dep[u] < dep[v]) swap(u, v); u = ancestork(u, dep[u] - dep[v]); if(u == v) return u; for(int i = L - 1; i >= 0; i--){ if(par[v][i] != par[u][i]){ v = par[v][i]; u = par[u][i]; } } int l = par[v][0]; return l; } pll distroot(ll x){ return query(tin[x]); } pll path(int u, int v){ pll res = {0, 0}; pll p1 = distroot(u), p2 = distroot(v), p3 = distroot(lca(u, v)); res.fi = p1.fi + p2.fi - p3.fi * 2; res.se = p1.se + p2.se - p3.se * 2; return res; } int goldpath(int u, int v){ return gold[u] + gold[v] - gold[lca(u, v)] * 2; } pll p[N]; int s[N], t[N]; ll x[N], y[N]; struct bs{ int l, r, mid, id; }; bs b[N]; int sus[N]; vector<bs> midcur[N]; void solve(){ int m, q; cin >> n >> m >> q; for(int i = 1; i < n; i++){ int u, v; cin >> u >> v; e[u].push_back(v); e[v].push_back(u); edge[i] = {u, v}; } for(int i = 1; i <= m; i++){ cin >> p[i].se >> p[i].fi; } sort(p + 1, p + m + 1); dfs(1, -1); dfs2(1, -1); for(int i = 1; i < n; i++){ int u = edge[i].fi, v = edge[i].se; if(tin[u] > tin[v]) swap(edge[i].fi, edge[i].se); } for(int i = 1; i <= m; i++){ gold[edge[p[i].se].se]++; } dfsgold(1, -1); for(int i = 1; i <= q; i++){ cin >> s[i] >> t[i] >> x[i] >> y[i]; b[i] = {0, m, 1, i}; } for(int z = 1; z < L; z++){ init(); for(int i = 1; i <= m; i++){ midcur[i].clear(); } for(int i = 1; i <= q; i++){ b[i].mid = (b[i].l + b[i].r + 1) / 2; midcur[b[i].mid].push_back(b[i]); } for(int i = 1; i <= m; i++){ int id = p[i].se; int u = edge[id].fi, v = edge[id].se; update(tin[v], tout[v], p[i].fi); for(auto [l, r, mid, id] : midcur[i]){ if(l == r) continue; u = s[id], v = t[id]; pll cur = path(u, v); if(cur.fi <= y[id]){ b[id].l = mid; sus[id] = cur.se; }else{ b[id].r = mid - 1; } } } } for(int i = 1; i <= q; i++){ int g = goldpath(s[i], t[i]); int silver_used = sus[i]; int gold_used = g - silver_used; if(gold_used > x[i]){ cout << -1 << endl; }else{ cout << x[i] - gold_used << endl; } } } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); if(fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); } int test = 1; //cin >> test; while(test--){ solve(); } }

Compilation message (stderr)

currencies.cpp: In function 'int main()':
currencies.cpp:216:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  216 |                 freopen(name".inp", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
currencies.cpp:217:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  217 |                 freopen(name".out", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...