Submission #916842

#	Time	Username	Problem	Language	Result	Execution time	Memory
916842		Yang8on	Two Currencies (JOI23_currencies)	C++14	10 / 100	2572 ms	378648 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 200005
#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, 19) 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, 19) if(gb(kc, j)) u = cha[u][j];
    if(u == v) return u;
    fid(j, 19, 0)
    {
        if(cha[u][j] != cha[v][j])
        {
            u = cha[u][j];
            v = cha[v][j];
        }
    }
    return cha[u][0];
}

const int maxs = 4000005;

int nNode;
int ver[maxs], L[maxs], R[maxs];
struct dl
{
    ll v, sl;
} st[maxs], lazy[maxs];

int newleaf(int id, int l, int r, ll val1, ll val2)
{
    int p = ++ nNode;
    L[p] = L[id], R[p] = R[id];
    st[p].v = st[id].v + 1ll * (r - l + 1) * val1;
    st[p].sl = st[id].sl + 1ll * (r - l + 1) * val2;
    lazy[p].v = lazy[id].v + val1;
    lazy[p].sl = lazy[id].sl + val2;

    return p;
}
void down(int id, int l, int r)
{
    if(lazy[id].v)
    {
        if(l != r)
        {
            int mid = (l + r) >> 1;
            L[id] = newleaf(L[id], l, mid, lazy[id].v, lazy[id].sl);
            R[id] = newleaf(R[id], mid + 1, r, lazy[id].v, lazy[id].sl);
        }
    }
    lazy[id].v = lazy[id].sl = 0;
}
int newparent(int lef, int rig)
{
    int p = ++ nNode;
    L[p] = lef, R[p] = rig;
    st[p].v = st[L[p]].v + st[R[p]].v;
    st[p].sl = st[L[p]].sl + st[R[p]].sl;
    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, 1ll);
    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].v;
    down(id, l, r);
    int mid = (l + r) >> 1;
    return get(L[id], i, l, mid) + get(R[id], i, 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 st[id].sl;
    down(id, l, r);
    int mid = (l + r) >> 1;
    return get2(L[id], i, l, mid) + get2(R[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);
    }

    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;
        }

        ll sum = get2(ver[m], in[v]) + get2(ver[m], in[u]) - 2ll * get2(ver[m], in[par]);
        ll use = get2(ver[r], in[v]) + get2(ver[r], in[u]) - 2ll * get2(ver[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;
}

/*
10 2 1
1 8
6 3
5 9
7 9
3 1
3 4
10 1
2 6
5 6

9 4
2 4

5 3 2 4
*/

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