Submission #751930

#	Time	Username	Problem	Language	Result	Execution time	Memory
751930		Spade1	Two Currencies (JOI23_currencies)	C++14	100 / 100	857 ms	118116 KiB

currencies

#include<bits/stdc++.h>
//#include <grader.h>
#define pii pair<int, int>
#define pll pair<long long, long long>
#define ll long long
#define ld long double
#define st first
#define nd second
#define pb push_back
#define INF INT_MAX
using namespace std;

const int N = 1e5 + 10;
const int L = log2(N)+1;

struct node{
    ll val, cnt;
    ll lc, rc;
}seg[20*N];

vector<pll> adj[N];
vector<ll> cost[N];
map<ll, ll> mp, rv;
ll up[N][L], lvl[N], cnt, root[N];

void update(ll &cur, ll l, ll r, ll x, ll val) {
    cnt++;
    seg[cnt] = seg[cur];
    cur = cnt;

    if (l==r) {
        seg[cur].val = val;
        seg[cur].cnt = 1;
        return;
    }
    int mid = (l+r)/2;
    if (x <= mid) update(seg[cur].lc, l, mid, x, val);
    else update(seg[cur].rc, mid+1, r, x, val);
    seg[cur].val = seg[seg[cur].rc].val + seg[seg[cur].lc].val;
    seg[cur].cnt = seg[seg[cur].rc].cnt + seg[seg[cur].lc].cnt;
}

ll query(ll curu, ll curv, ll curc, ll l, ll r, ll x, ll ans) {
    if (l==r) {
        if (x >= seg[curu].val + seg[curv].val - 2*seg[curc].val)
            return ans + seg[curu].cnt + seg[curv].cnt - 2*seg[curc].cnt;
        else
            return ans;
    }
    ll mid = (l+r)/2;
    ll nxt = seg[seg[curu].lc].val + seg[seg[curv].lc].val - 2*seg[seg[curc].lc].val;
    ll lft = seg[seg[curu].lc].cnt + seg[seg[curv].lc].cnt - 2*seg[seg[curc].lc].cnt;
    if (nxt > x) return query(seg[curu].lc, seg[curv].lc, seg[curc].lc, l, mid, x, ans);
    else return query(seg[curu].rc, seg[curv].rc, seg[curc].rc, mid+1, r, x-nxt, ans+lft);
}

void dfs(ll a, ll prt) {
    up[a][0] = prt; lvl[a] = lvl[prt]+1;
    for (int i = 1; i < L; ++i) up[a][i] = up[up[a][i-1]][i-1];
    for (auto [b, idx] : adj[a]) if (b != prt) dfs(b, a);
}

ll lca(ll a, ll b) {
    if (lvl[a] < lvl[b]) swap(a, b);
    ll j = lvl[a]-lvl[b];
    for (int i = 0; i < L; ++i) if (j&(1<<i)) a = up[a][i];
    if (a==b) return a;
    for (int i = L-1; i >= 0; --i) if (up[a][i] != up[b][i]) a = up[a][i], b = up[b][i];
    return up[a][0];
}

void build(int a, int prt) {
    for (auto [b, i] : adj[a]) {
        if (b == prt) continue;
        root[b] = root[a];
        for (auto c : cost[i]) update(root[b], 1, 100000, mp[c], rv[c]);
        build(b, a);
    }
}

void solve() {
    int n, m, q; cin >> n >> m >> q;
    for (int i = 1; i < n; ++i) {
        ll a, b; cin >> a >> b;
        adj[a].pb({b, i});
        adj[b].pb({a, i});
    }
    vector<pll> v; ll tmp = 0;
    for (int i = 1; i <= m; ++i) {
        ll p, c; cin >> p >> c;
        cost[p].pb(i); v.pb({c, i});
    }
    sort(v.begin(), v.end());
    for (auto i : v) mp[i.nd] = ++tmp, rv[i.nd] = i.st;
    dfs(1, 0);
    build(1, 0);
    while (q--) {
        ll s, t, x, y; cin >> s >> t >> x >> y;
        ll c = lca(s, t);
        ll rmn = query(root[s], root[t], root[c], 1, 100000, 1e18, 0) - query(root[s], root[t], root[c], 1, 100000, y, 0);
        if (rmn > x) cout << -1 << '\n';
        else cout << x-rmn << '\n';
    }
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(NULL);
    int t = 1;
//    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

Compilation message (stderr)

currencies.cpp: In function 'void dfs(long long int, long long int)':
currencies.cpp:60:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   60 |     for (auto [b, idx] : adj[a]) if (b != prt) dfs(b, a);
      |               ^
currencies.cpp: In function 'void build(int, int)':
currencies.cpp:73:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   73 |     for (auto [b, i] : adj[a]) {
      |               ^

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