Submission #793166

#	Time	Username	Problem	Language	Result	Execution time	Memory
793166		phoenix	Two Currencies (JOI23_currencies)	C++17	38 / 100	421 ms	32348 KiB

currencies

#include<bits/stdc++.h>

using namespace std;
using ll = long long;

struct citizen {
    int s, t;
    ll x, y;
    int inx;
};

struct edge {
    int to, i;
};

int n, m, q;
vector<pair<int, int>> edges;
vector<pair<int, int>> checkpoints;
vector<citizen> citizens;
vector<int> answers;

namespace Subtask1 {
    const int N = 1e5 + 10;
    vector<edge> g[N];
    int depth[N], pre[N], T;
    int inx[N] = {};
    ll C;
    void precalc(int s, int p) {
        pre[s] = p;
        for(auto [to, i] : g[s]) {
            if(to == p) continue;
            depth[to] = depth[s] + 1;
            inx[to] = i;
            precalc(to, s);
        }
    }
    void init() {
        int koll = 0;
        for(auto [u, v] : edges) {
            g[u].push_back({v, koll});
            g[v].push_back({u, koll});
            koll++;
        }
        precalc(1, 1);
        for(citizen cit : citizens) {
            set<int> ee;
            int u = cit.s, v = cit.t;
            while(u != v) {
                if(depth[u] >= depth[v]) {
                    ee.insert(inx[u]);
                    u = pre[u];
                } else {
                    ee.insert(inx[v]);
                    v = pre[v];
                }
            }
            set<ll> st;
            ll sum = 0, k = 0;
            for(auto [p, c] : checkpoints) {
                if(!ee.count(p)) continue;
                st.insert(c);
                sum += c;
                if(sum > cit.y) {
                    k++;
                    sum -= *(--st.end());
                    st.erase(--st.end());
                }
            }
            answers[cit.inx] = (cit.x < k ? -1 : cit.x - k);
        }
    }
};

namespace Subtask2 {
    const int N = 1e5 + 10;
    vector<int> g[N];
    int tin[N], tout[N], anc[N][17], T;
    int f[N] = {};
    int cnt[N] = {};
    ll C;
    void precalc(int s, int p) {
        tin[s] = T++;
        anc[s][0] = p;
        cnt[s] = cnt[p] + f[s]; 
        for(int i = 1; i < 17; i++) 
            anc[s][i] = anc[anc[s][i - 1]][i - 1];
        for(int to : g[s]) {
            if(to == p) continue;
            precalc(to, s);
        }
        tout[s] = T++;
    }
    bool up(int u, int v) {
        return tin[u] <= tin[v] && tout[u] >= tout[v];
    }
    int lca(int u, int v) {
        if(up(u, v)) return u;
        if(up(v, u)) return v;
        for(int i = 16; i >= 0; i--) {
            if(!up(anc[u][i], v)) u = anc[u][i];
        }
        return anc[u][0];
    }
    void init() {
        for(auto [u, v] : edges) {
            g[u].push_back(v);
            g[v].push_back(u);
        }
        precalc(1, 1);
        
        for(auto [p, c] : checkpoints) {
            auto [u, v] = edges[p];
            if(tin[u] > tin[v]) swap(u, v);
            f[v]++;
            C = c;
        }
        precalc(1, 1);
        
        for(citizen c : citizens) {
            int u = lca(c.s, c.t);
            int k = cnt[c.s] + cnt[c.t] - 2 * cnt[u];
            if(C == 0) answers[c.inx] = c.x;
            else {
                int ans = c.x - max(k - c.y / C, 0ll);
                if(ans < 0) ans = -1;
                answers[c.inx] = ans;
            }
            // cout << c.inx << ' ' << ans << '\n';
        }
    } 
};

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin >> n >> m >> q;
    for(int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        edges.push_back({u, v});
    }
    for(int i = 0; i < m; i++) {
        int p, c;
        cin >> p >> c;
        p--;
        checkpoints.push_back({p, c});
    }
    for(int i = 0; i < q; i++) {
        citizen s;
        cin >> s.s >> s.t >> s.x >> s.y;
        s.inx = i;
        citizens.push_back(s);
    }
    answers.resize(q);
    if(n <= 2000) {
        Subtask1::init();
    } else {
        Subtask2::init();
    }
    for(int c : answers) 
        cout << c << '\n';
}

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