Submission #994284

#	Time	Username	Problem	Language	Result	Execution time	Memory
994284		onbert	Two Currencies (JOI23_currencies)	C++17	100 / 100	4594 ms	221740 KiB

currencies

#include <bits/stdc++.h>
using namespace std;
#define int long long
struct node {
    int val1, val2, lpt, rpt;
};
const int maxn = 1e5 + 5, lgn = 18, maxN = 4e5 + 5;
int n, m, q;
vector<pair<int,int>> adj[maxn];
vector<int> ck[maxn];
int fa[maxn], sz[maxn], d[maxn];
pair<int,int> a[maxn];

bool cmp(pair<int,int> x, pair<int,int> y) {
    return sz[x.first] > sz[y.first];
}

void dfs1(int u) {
    for (auto [v, id]:adj[u]) {
        adj[v].erase(find(adj[v].begin(), adj[v].end(), make_pair(u, id)));
        fa[v] = u, sz[v] = ck[id].size(), d[v] = d[u]+1;
        dfs1(v);
        sz[u] += sz[v];
    }
    sort(adj[u].begin(), adj[u].end(), cmp);
}

int newid[maxn], cnter = 0;
void dfs2(int u) {
    for (auto [v, id]:adj[u]) {
        for (auto &j:ck[id]) {
            cnter++;
            newid[j] = cnter;
            j = newid[j];
        }
        dfs2(v);
    }
}

pair<int, vector<pair<int,int>>> lift[maxn][lgn];
void dfs3(int u) {
    for (int i=1;i<lgn;i++) {
        if (lift[u][i-1].first==-1 || lift[lift[u][i-1].first][i-1].first==-1) break;
        lift[u][i].first = lift[lift[u][i-1].first][i-1].first;
        lift[u][i].second = lift[u][i-1].second;
        for (auto [l, r]:lift[lift[u][i-1].first][i-1].second) {
            if (lift[u][i].second.size()>0 && r+1 == lift[u][i].second.back().first) lift[u][i].second.back().first = l;
            else lift[u][i].second.push_back({l, r});
        }
        // assert(lift[u][i].second.size() <= 30);
    }
    for (auto [v, id]:adj[u]) {
        lift[v][0].first = u;
        if (ck[id].size()!=0) lift[v][0].second.push_back({ck[id][0], ck[id].back()});
        dfs3(v);
    }
}

vector<node> seg[maxN];
void build(int id, int l, int r) {
    seg[id] = {{0, 0, 0, 0}};
    if (l==r) return;
    int mid = (l+r)/2;
    build(id*2, l, mid);
    build(id*2+1, mid+1, r);
}
void update(int id, int l, int r, int target, int val1, int val2) {
    if (r<target || target<l) return;
    if (l==r) {
        seg[id].push_back({val1, val2, -1, -1});
        return;
    }
    int mid = (l+r)/2;
    update(id*2, l, mid, target, val1, val2); update(id*2+1, mid+1, r, target, val1, val2);
    node nxt = {0, 0, (int)seg[id*2].size()-1, (int)seg[id*2+1].size()-1};
    nxt.val1 = seg[id*2].back().val1 + seg[id*2+1].back().val1;
    nxt.val2 = seg[id*2].back().val2 + seg[id*2+1].back().val2;
    seg[id].push_back(nxt);
}
pair<int,int> qry(int id, int pt, int l, int r, int findl, int findr) {
    if (findl<=l && r<=findr) return {seg[id][pt].val1, seg[id][pt].val2};
    if (r<findl || findr<l) return {0, 0};
    int mid = (l+r)/2, lpt = seg[id][pt].lpt, rpt = seg[id][pt].rpt;
    pair<int,int> lhs = qry(id*2, lpt, l, mid, findl, findr);
    pair<int,int> rhs = qry(id*2+1, rpt, mid+1, r, findl, findr);
    return {lhs.first + rhs.first, lhs.second + rhs.second};
}

vector<pair<int,int>> qry2(int u, int v) {
    if (d[u] > d[v]) swap(u, v);
    vector<pair<int,int>> U, V;
    for (int i=lgn-1;i>=0;i--) if (d[v] - (1<<i) >= d[u]) {
        for (auto [l, r]:lift[v][i].second) {
            if (V.size() > 0 && r+1 == V.back().first) V.back().first = l;
            else V.push_back({l, r});
        }
        v = lift[v][i].first;
    }
    if (u==v) return V;
    for (int i=lgn-1;i>=0;i--) if (lift[u][i].first!=lift[v][i].first) {
        for (auto [l, r]:lift[u][i].second) {
            if (U.size() > 0 && r+1 == U.back().first) U.back().first = l;
            else U.push_back({l, r});
        }
        for (auto [l, r]:lift[v][i].second) {
            if (V.size() > 0 && r+1 == V.back().first) V.back().first = l;
            else V.push_back({l, r});
        }
        u = lift[u][i].first, v = lift[v][i].first;
    }
    for (auto [l, r]:lift[u][0].second) {
        if (U.size() > 0 && r+1 == U.back().first) U.back().first = l;
        else U.push_back({l, r});
    }
    for (auto [l, r]:lift[v][0].second) {
        if (V.size() > 0 && r+1 == V.back().first) V.back().first = l;
        else V.push_back({l, r});
    }
    for (auto [l, r]:V) U.push_back({l, r});
    return U;
}

signed main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m >> q;
    for (int i=1;i<n;i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back({v, i});
        adj[v].push_back({u, i});
    }
    int A[m+1];
    for (int i=1;i<=m;i++) {
        int loc;
        cin >> loc >> A[i];
        ck[loc].push_back(i);
    }
    for (int i=1;i<=n;i++) fa[i] = -2;
    fa[1] = -1, sz[1] = 0, d[1] = 0;
    dfs1(1);
    dfs2(1);
    // for (int i=1;i<=m;i++) cout << newid[i] << " "; cout << endl;
    for (int i=1;i<=m;i++) a[newid[i]] = {A[i], newid[i]};
    for (int i=1;i<=n;i++) for (int j=0;j<lgn;j++) lift[i][j] = {-1, {}};
    dfs3(1);
    
    sort(a+1, a+m+1);
    build(1, 1, m);
    for (int i=1;i<=m;i++) update(1, 1, m, a[i].second, a[i].first, 1);
    // for (int i=1;i<=n;i++) {
    //     cout << i << endl;
    //     for (auto [l, r]:lift[i][1].second) cout << l << " " << r << endl;
    //     cout << endl;
    // }
    // cout << "test" << endl;
    while (q--) {
        int u, v, x, y;
        cin >> u >> v >> x >> y;
        vector<pair<int,int>> vec = qry2(u, v);
        // for (auto [l, r]:vec) cout << l << " " << r << endl;
        int L = 0, R = m;
        while (L<R) {
            int mid = (L+R+1)/2, sum = 0;
            for (auto [l, r]:vec) sum += qry(1, mid, 1, m, l, r).first;
            if (sum > y) R = mid-1;
            else L = mid;
        }
        int sum = 0;
        for (auto [l, r]:vec) sum += qry(1, m, 1, m, l, r).second - qry(1, L, 1, m, l, r).second;
        x -= sum;
        if (x<0) cout << -1 << "\n";
        else cout << x << "\n";
    }
}

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