Submission #916806

#	Time	Username	Problem	Language	Result	Execution time	Memory
916806		Yang8on	Two Currencies (JOI23_currencies)	C++17	10 / 100	4062 ms	757396 KiB

currencies

#include <bits/stdc++.h>
#define nosg "Two Currencies"
#define fi(i, a, b) for(int i = a; i <= b; i++)
#define fid(i, a, b) for(int i = a; i >= b; i--)
#define ll long long
#define maxn 6000005
#define gb(i, j) ((i >> j) & 1)
#define pii pair<int, int>
#define f first
#define s second

using namespace std;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

ll GetRandom(ll l, ll r)
{
    return uniform_int_distribution<ll> (l, r) (rng);
}

int n, m, q;
pii edge[maxn], tram[maxn];
vector<int> o[maxn];

int cnt;
int in[maxn], out[maxn];
int h[maxn], cha[maxn][20];

void dfs(int u, int par)
{
    in[u] = ++ cnt;
    for(int v : o[u])
    {
        if(v == par) continue;
        h[v] = h[u] + 1;
        cha[v][0] = u;
        fi(j, 1, 17) cha[v][j] = cha[cha[v][j - 1]][j - 1];
        dfs(v, u);
    }
    out[u] = cnt;
}

int lca(int u, int v)
{
    if(h[u] < h[v]) swap(u, v);
    int kc = h[u] - h[v];
    fi(j, 0, 17) if(gb(kc, j)) u = cha[u][j];
    if(u == v) return u;
    fid(j, 17, 0)
    {
        if(cha[u][j] != cha[v][j])
        {
            u = cha[u][j];
            v = cha[v][j];
        }
    }
    return cha[u][0];
}

int nNode;
int ver[maxn], L[maxn], R[maxn];
ll st[maxn], lazy[maxn];
int newleaf(int id, int l, int r, ll val)
{
    int p = ++ nNode;
    L[p] = L[id], R[p] = R[id];
    st[p] = st[id] + 1ll * (r - l + 1) * val;
    lazy[p] = lazy[id] + val;

    return p;
}
void down(int id, int l, int r)
{
    if(lazy[id])
    {
        if(l != r)
        {
            int mid = (l + r) >> 1;
            L[id] = newleaf(L[id], l, mid, lazy[id]);
            R[id] = newleaf(R[id], mid + 1, r, lazy[id]);
        }
    }
    lazy[id] = 0;
}
int newparent(int lef, int rig)
{
    int p = ++ nNode;
    L[p] = lef, R[p] = rig;
    st[p] = st[L[p]] + st[R[p]];
    return p;
}
int update(int oid, int u, int v, ll val, int l = 1, int r = n)
{
    if(v < l || r < u) return oid;
    if(u <= l && r <= v) return newleaf(oid, l, r, val);
    down(oid, l, r);
    int mid = (l + r) >> 1;
    return newparent( update(L[oid], u, v, val, l, mid), update(R[oid], u, v, val, mid + 1, r) );
}
ll get(int id, int i, int l = 1, int r = n)
{
    if(i < l || r < i) return 0;
    if(l == r) return st[id];
    down(id, l, r);
    int mid = (l + r) >> 1;
    return get(L[id], i, l, mid) + get(R[id], i, mid + 1, r);
}


int nNode2;
int ver2[maxn], L2[maxn], R2[maxn];
ll st2[maxn], lazy2[maxn];
int newleaf2(int id, int l, int r, ll val)
{
    int p = ++ nNode2;
    L2[p] = L2[id], R2[p] = R2[id];
    st2[p] = st2[id] + 1ll * (r - l + 1) * val;
    lazy2[p] = lazy2[id] + val;

    return p;
}
void down2(int id, int l, int r)
{
    if(lazy2[id])
    {
        if(l != r)
        {
            int mid = (l + r) >> 1;
            L2[id] = newleaf2(L2[id], l, mid, lazy2[id]);
            R2[id] = newleaf2(R2[id], mid + 1, r, lazy2[id]);
        }
    }
    lazy2[id] = 0;
}
int newparent2(int lef, int rig)
{
    int p = ++ nNode2;
    L2[p] = lef, R2[p] = rig;
    st2[p] = st2[L2[p]] + st2[R2[p]];
    return p;
}
int update2(int oid, int u, int v, int l = 1, int r = n)
{
    if(v < l || r < u) return oid;
    if(u <= l && r <= v) return newleaf2(oid, l, r, 1);
    down2(oid, l, r);
    int mid = (l + r) >> 1;
    return newparent2( update2(L2[oid], u, v, l, mid), update2(R2[oid], u, v, mid + 1, r) );
}
ll get2(int id, int i, int l = 1, int r = n)
{
    if(i < l || r < i) return 0;
    if(l == r) return st2[id];
    down2(id, l, r);
    int mid = (l + r) >> 1;
    return get2(L2[id], i, l, mid) + get2(R2[id], i, mid + 1, r);
}

int main()
{
//    freopen(nosg".inp","r",stdin);
//    freopen(nosg".out","w",stdout);

    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n >> m >> q;
    fi(i, 1, n - 1)
    {
        cin >> edge[i].f >> edge[i].s;
        int u = edge[i].f, v = edge[i].s;
        o[u].push_back(v);
        o[v].push_back(u);
    }

    dfs(1, -1);

    fi(i, 1, m) cin >> tram[i].f >> tram[i].s;

    sort(tram + 1, tram + m + 1, [](pii x, pii y) {
            return x.s < y.s;
         });

    fi(i, 1, m)
    {
        int j = tram[i].f, val = tram[i].s;
        int u = edge[j].f, v = edge[j].s;

        if(h[u] > h[v]) swap(u, v);

        ver[i] = update(ver[i - 1], in[v], out[v], 1ll * val);
        ver2[i] = update2(ver2[i - 1], in[v], out[v]);
    }

    fi(i, 1, q)
    {
        int u, v;
        ll S, G;

        cin >> u >> v >> G >> S;

        if(h[u] > h[v]) swap(u, v);
        int par = lca(u, v);

        int l = 1, r = m;
        while(l <= r)
        {
            int mid = (l + r) >> 1;
            if(get(ver[mid], in[v]) + get(ver[mid], in[u]) - 2ll * get(ver[mid], in[par]) <= S) l = mid + 1;
            else r = mid - 1;
        }

        int sum = get2(ver2[m], in[v]) + get2(ver2[m], in[u]) - 2ll * get2(ver2[m], in[par]);
        int use = get2(ver2[r], in[v]) + get2(ver2[r], in[u]) - 2ll * get2(ver2[r], in[par]);

        cout << (G - (sum - use) >= 0 ? G - (sum - use) : -1) << '\n';
    }


    /// ------------------check time!-----------------///
    cerr << "\n" << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
    return 0;
}

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