Submission #729336

#	Time	Username	Problem	Language	Result	Execution time	Memory
729336		stevancv	Two Currencies (JOI23_currencies)	C++14	100 / 100	478 ms	71116 KiB

currencies

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define sp ' '
#define en '\n'
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
using namespace std;
const int N = 1e5 + 2;
const int M = 20 * N;
const int inf = 1e9;
vector<pair<int, int>> g[N];
int par[N][17], in[N], out[N], tsz, psz;
void Dfs(int s, int e) {
    par[s][0] = e;
    for (int i = 1; i < 17; i++) par[s][i] = par[par[s][i - 1]][i - 1];
    in[s] = ++tsz;
    for (auto u : g[s]) {
        if (u.first != e) {
            Dfs(u.first, s);
        }
    }
    out[s] = tsz;
}
bool Ancestor(int u, int v) {
    return in[u] <= in[v] && out[v] <= out[u];
}
int Lca(int u, int v) {
    if (Ancestor(u, v)) return u;
    if (Ancestor(v, u)) return v;
    for (int i = 16; i >= 0; i--) {
        if (par[u][i] && !Ancestor(par[u][i], v)) u = par[u][i];
    }
    return par[u][0];
}
vector<pair<int, int>> dat[N];
vector<int> order, inv;
ll st[M];
int lc[M], rc[M], cnt[M], root[N], uk;
map<int, int> gde;
void Add(int &c, int pc, int l, int r, int pos, int x, int y) {
    c = ++tsz; st[c] = st[pc] + x; lc[c] = lc[pc]; rc[c] = rc[pc]; cnt[c] = cnt[pc] + y;
    if (l == r) return;
    int mid = l + r >> 1;
    if (pos <= mid) Add(lc[c], lc[pc], l, mid, pos, x, y);
    else Add(rc[c], rc[pc], mid + 1, r, pos, x, y);
}
void Find(int a, int b, int c, int l, int r, ll s) {
    ll S = st[a] + st[b] - 2 * st[c];
    int C = cnt[a] + cnt[b] - 2 * cnt[c];
    if (l == r) {
        if (S <= s) uk -= C;
        return;
    }
    int mid = l + r >> 1;
    ll Sl = st[lc[a]] + st[lc[b]] - 2 * st[lc[c]];
    int Cl = cnt[lc[a]] + cnt[lc[b]] - 2 * cnt[lc[c]];
    if (Sl < s) {
        uk -= Cl;
        Find(rc[a], rc[b], rc[c], mid + 1, r, s - Sl);
    }
    else Find(lc[a], lc[b], lc[c], l, mid, s);
}
void Dfs1(int s, int e) {
    for (auto u : g[s]) {
        if (u.first == e) continue;
        root[u.first] = root[s];
        int nesto = u.second;
        for (int i = 0; i < dat[nesto].size(); i++) {
            auto uu = dat[nesto][i];
            Add(root[u.first], root[u.first], 0, psz, inv[uu.second], uu.first, 1);
        }
        Dfs1(u.first, s);
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, m, q;
    cin >> n >> m >> q;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back({v, i});
        g[v].push_back({u, i});
    }
    Dfs(1, 0);
    vector<int> vvv(m);
    for (int i = 0; i < m; i++) {
        int u;
        cin >> u >> vvv[i];
        dat[u].push_back({vvv[i], i});
    }
    order.resize(m);
    inv.resize(m);
    iota(order.begin(), order.end(), 0);
    sort(order.begin(), order.end(), [&] (int i, int j) {
        return vvv[i] < vvv[j];
    });
    for (int i = 0; i < m; i++) inv[order[i]] = i;
    psz = m - 1;
    tsz = 0;
    Dfs1(1, 0);
    while (q--) {
        int s, t, x; ll y;
        cin >> s >> t >> x >> y;
        int lca = Lca(s, t);
        uk = cnt[root[s]] + cnt[root[t]] - 2 * cnt[root[lca]];
        Find(root[s], root[t], root[lca], 0, psz, y);
        cout << max(x - uk, -1) << en;
    }
    return 0;
}

Compilation message (stderr)

currencies.cpp: In function 'void Add(int&, int, int, int, int, int, int)':
currencies.cpp:44:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   44 |     int mid = l + r >> 1;
      |               ~~^~~
currencies.cpp: In function 'void Find(int, int, int, int, int, long long int)':
currencies.cpp:55:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   55 |     int mid = l + r >> 1;
      |               ~~^~~
currencies.cpp: In function 'void Dfs1(int, int)':
currencies.cpp:69:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |         for (int i = 0; i < dat[nesto].size(); i++) {
      |                         ~~^~~~~~~~~~~~~~~~~~~

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