Submission #792553

#TimeUsernameProblemLanguageResultExecution timeMemory
792553anhduc2701Two Currencies (JOI23_currencies)C++17
0 / 100
8 ms7764 KiB
/* #pragma GCC optimize("Ofast") #pragma GCC target("avx,avx2,fma") #pragma GCC optimize("unroll-loops") */ #include <bits/stdc++.h> using namespace std; #define all(x) x.begin(), x.end() #define len(x) ll(x.size()) #define eb emplace_back #define PI acos(-1.0) #define fi first #define se second #define mp make_pair #define pb push_back #define MIN(v) *min_element(all(v)) #define MAX(v) *max_element(all(v)) #define BIT(x, i) (1 & ((x) >> (i))) #define MASK(x) (1LL << (x)) #define task "tnc" #define rep(i, n) for (int i = 0; i < (n); i++) #define rep1(i, n) for (int i = 1; i <= (n); i++) typedef long long ll; typedef long double ld; const ll INF = 1e18; const int maxn = 1e5 + 5; const int mod = 1e9 + 7; const int mo = 998244353; using pi = pair<ll, ll>; using vi = vector<ll>; using pii = pair<pair<ll, ll>, ll>; mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count()); int n, m, q; vector<int> G[maxn]; struct ask { int s, t, x, y; } que[maxn]; int p[maxn]; int c[maxn]; struct cp { int p, c; bool operator<(const cp &x) { return c < x.c; } } ch[maxn]; struct BIT { ll bit[maxn]; void init() { memset(bit, 0, sizeof(bit)); } void upd(int id, ll val) { for (id; id <= n; id += id & -id) { bit[id] += val; } } ll get(int id) { ll res = 0; for (id; id >= 1; id -= id & -id) { res += bit[id]; } return res; } } A, B; int tin[maxn]; int tout[maxn]; int s = 0; int par[maxn]; pair<int, int> rmq[maxn][20]; int eu1[maxn]; int tin1[maxn]; int tout1[maxn]; int s1 = 0; void dfs(int u, int pa) { tin[u] = ++s; tin1[u] = ++s1; eu1[s1] = u; for (auto v : G[u]) { if (v == pa) continue; par[v] = u; dfs(v, u); eu1[++s1] = u; } tout[u] = s; } void init() { for (int i = 1; i <= s1; i++) { rmq[i][0] = {tin1[eu1[i]], eu1[i]}; } for (int i = 1; (1 << i) <= s1; i++) { for (int j = 1; j + (1 << i) - 1 <= s1; j++) { rmq[j][i] = min(rmq[j + (1 << (i - 1))][i - 1], rmq[j][i - 1]); } } } int LCA(int u, int v) { if (tin1[u] > tin1[v]) swap(u, v); int dis = 31 - __builtin_clz(tin1[v] - tin1[u] + 1); return min(rmq[tin1[u]][dis], rmq[tin1[v] - (1 << dis) + 1][dis]).se; } int l[maxn]; int ans[maxn]; int r[maxn]; pair<int, int> ed[maxn]; vector<int> K[maxn]; void solve() { cin >> n >> m >> q; for (int i = 1; i < n; i++) { int a, b; cin >> a >> b; ed[i].fi = a; ed[i].se = b; G[a].pb(b); G[b].pb(a); } dfs(1, -1); init(); for (int i = 1; i <= m; i++) { cin >> ch[i].p >> ch[i].c; if (par[ed[ch[i].p].fi] == ed[ch[i].p].se) { ch[i].p = ed[ch[i].p].fi; } else { ch[i].p = ed[ch[i].p].se; } } sort(ch + 1, ch + 1 + m); for (int i = 1; i <= q; i++) { cin >> que[i].s >> que[i].t >> que[i].x >> que[i].y; ans[i] = 1e9; l[i] = 0; r[i] = m; } for (int _ = 1; _ <= 18; _++) { for (int i = 1; i <= q; i++) { if (l[i] <= r[i]) { int mid = (l[i] + r[i]) >> 1; K[mid].pb(i); } } A.init(); B.init(); for (int i = 1; i <= m; i++) { A.upd(tin[ch[i].p], 1); A.upd(tout[ch[i].p] + 1, -1); } for (int i = 0; i <= m; i++) { if (i) { B.upd(tin[ch[i].p], ch[i].c); B.upd(tout[ch[i].p] + 1, -ch[i].c); // cout << tin[ch[i].p] << " " << tout[ch[i].p] << " " << ch[i].c << "\n"; A.upd(tin[ch[i].p], -1); A.upd(tout[ch[i].p] + 1, 1); } for (auto v : K[i]) { int u = LCA(que[v].s, que[v].t); int silver = B.get(tin[que[v].s]) + B.get(tin[que[v].t]) - 2 * B.get(tin[u]); // cout << que[v].s << " " << que[v].t << " " << u << "\n"; int gold = A.get(tin[que[v].s]) + A.get(tin[que[v].t]) - 2 * A.get(tin[u]); if (silver <= que[v].y) { ans[v] = gold; l[v] = i + 1; } else { r[v] = i - 1; } } K[i].clear(); } } for (int i = 1; i <= q; i++) { if (ans[i] <= que[i].x) { cout << que[i].x - ans[i] << "\n"; } else { cout << "-1\n"; } } } signed main() { cin.tie(0), cout.tie(0)->sync_with_stdio(0); solve(); }

Compilation message (stderr)

currencies.cpp: In member function 'void BIT::upd(int, ll)':
currencies.cpp:58:14: warning: statement has no effect [-Wunused-value]
   58 |         for (id; id <= n; id += id & -id)
      |              ^~
currencies.cpp: In member function 'll BIT::get(int)':
currencies.cpp:66:14: warning: statement has no effect [-Wunused-value]
   66 |         for (id; id >= 1; id -= id & -id)
      |              ^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...