Submission #792682

#	Time	Username	Problem	Language	Result	Execution time	Memory
792682		vjudge1	Two Currencies (JOI23_currencies)	C++17	0 / 100	2 ms	2672 KiB

currencies

#include<bits/stdc++.h>

using namespace std;
using ll = long long;

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

ll n, m, q;
vector<pair<ll, ll>> edges;
vector<pair<ll, ll>> checkpolls;
vector<citizen> citizens;
vector<ll> answers;

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

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