Submission #991573

#	Time	Username	Problem	Language	Result	Execution time	Memory
991573		blackslex	Two Currencies (JOI23_currencies)	C++17	0 / 100	9 ms	25436 KiB

currencies

#include<bits/stdc++.h>

using namespace std;
using ll = long long;
using pii = pair<int, int>;

const int N = 1e5 + 5, K = 22;
int n, m, q, x, y, c[N], ca[N], idx[N], dp[K][N], dep[N], d[N], par[N];
vector<pii> v[N];
vector<int> rc;

struct node {
    ll val;
    int cnt;
    node *l, *r;
    node() : val(0LL), cnt(0), l(nullptr), r(nullptr) {}
    node(ll val, int cnt) : val(val), cnt(0), l(nullptr), r(nullptr) {}
};

typedef node* pnode;
pnode rt[N];

void build (int l, int r, pnode &cur) {
    cur = new node();
    if (l == r) return;
    int mid = (l + r) >> 1;
    build(l, mid, cur->l);
    build(mid + 1, r, cur->r);
}

void upd (int l, int r, pnode &cur, pnode par, int pos, int val) {
    cur = new node(*par);
    cur->val += val;
    cur->cnt++;
    if (l == r) return;
    int mid = (l + r) >> 1;
    if (pos <= mid) upd(l, mid, cur->l, par->l, pos, val);
    else upd(mid + 1, r, cur->r, par->r, pos, val);
}

ll qr (int l, int r, pnode add, pnode add2, pnode del, ll val) {
    if (l == r) return min((ll) add->cnt + add2->cnt - del->cnt * 2, val / rc[l]);
    int mid = (l + r) >> 1;
    ll cval = add->l->val + add2->l->val - del->l->val * 2;
    int ccnt = add->l->cnt + add2->l->cnt - del->l->cnt * 2;
    if (cval >= val) return qr(l, mid, add->l, add2->l, del->l, val);
    else return ccnt + qr(mid + 1, r, add->r, add2->r, del->r, val - cval);
}

void dfs (int cur, int par) {
    dp[0][cur] = par; dep[cur] = dep[par] + 1; d[cur] = d[par] + 1; ::par[cur] = par;
    for (auto &[x, y]: v[cur]) {
        if (par == x) continue;
        dfs(x, cur); ca[x] = y;
    }
}

int lca (int a, int b) {
    if (dep[b] > dep[a]) swap(a, b);
    for (int i = K - 1; i >= 0; i--) if (dep[dp[i][a]] >= dep[b]) a = dp[i][a];
    if (a == b) return a;
    for (int i = K - 1; i >= 0; i--) if (dp[i][a] != dp[i][b]) a = dp[i][a], b = dp[i][b];
    return dp[0][a];
}

void dfs2 (int cur, int par) {
    upd(1, n, rt[cur], rt[par], idx[ca[cur]], rc[ca[cur]]);
    for (auto &[x, y]: v[cur]) {
        if (par == x) continue;
        dfs2(x, cur);
    }
}

void solve() {
    int s, t;
    scanf("%d %d %d %d", &s, &t, &x, &y);
    int lc = lca(s, t);
    int cdist = d[s] + d[t] - d[lc] * 2;
    int cqr = qr(1, n, rt[s], rt[t], rt[lc], y);
    int cw = cdist - cqr;
    printf("%d\n", max(x - cw, -1));
}

int main() {
    scanf("%d %d %d", &n, &m, &q);
    for (int i = 1; i < n; i++) scanf("%d %d", &x, &y), v[x].emplace_back(y, i), v[y].emplace_back(x, i);
    while (m--) scanf("%d %d", &x, &y), c[x] += y;
    for (int i = 1; i < n; i++) if (c[i]) rc.emplace_back(c[i]); rc.emplace_back(0);
    sort(rc.begin(), rc.end());
    for (int i = 1; i < n; i++) idx[i] = lower_bound(rc.begin(), rc.end(), c[i]) - rc.begin();
    dfs(1, 0);
    for (int i = 1; i < K; i++) {
        for (int j = 1; j <= n; j++) dp[i][j] = dp[i - 1][dp[i - 1][j]];
    }
    build(1, n, rt[0]); dfs2(1, 0);
    while (q--) solve();
}

Compilation message (stderr)

currencies.cpp: In function 'int main()':
currencies.cpp:88:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   88 |     for (int i = 1; i < n; i++) if (c[i]) rc.emplace_back(c[i]); rc.emplace_back(0);
      |     ^~~
currencies.cpp:88:66: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   88 |     for (int i = 1; i < n; i++) if (c[i]) rc.emplace_back(c[i]); rc.emplace_back(0);
      |                                                                  ^~
currencies.cpp: In function 'void solve()':
currencies.cpp:76:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |     scanf("%d %d %d %d", &s, &t, &x, &y);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
currencies.cpp: In function 'int main()':
currencies.cpp:85:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   85 |     scanf("%d %d %d", &n, &m, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
currencies.cpp:86:38: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   86 |     for (int i = 1; i < n; i++) scanf("%d %d", &x, &y), v[x].emplace_back(y, i), v[y].emplace_back(x, i);
      |                                 ~~~~~^~~~~~~~~~~~~~~~~
currencies.cpp:87:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   87 |     while (m--) scanf("%d %d", &x, &y), c[x] += y;
      |                 ~~~~~^~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 28
• Subtask 3: 0 / 30
• Subtask 4: 0 / 32