Submission #1110662

#	Time	Username	Problem	Language	Result	Execution time	Memory
1110662		mispertion	Two Currencies (JOI23_currencies)	C++17	100 / 100	2576 ms	68384 KiB

currencies

#include <bits/stdc++.h>

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
#define F first
#define S second
#define pb push_back
#define sz(x) (int)x.size()

const ld PI = 3.1415926535;
const int N = 5e5 + 1;
const int M = 1e7 + 1;
ll mod =  998244353;
const int infi = 1e9;
const ll infl = 1e16;
const int P = 31;

int mult(int a, int b) { return a * 1LL * b % mod; }

int sum(int a, int b) {
    if (a + b < 0) return a + b + mod;
    if (a + b >= mod) return a + b - mod;
    return a + b;
}

ll binpow(ll a, ll n) {
    if (n == 0) return 1;
    if (n % 2 == 1) {
        return binpow(a, n - 1) * a % mod;
    } else {
        ll b = binpow(a, n / 2);
        return b * b % mod;
    }
}
struct segtree{
    vector<ll> sm;
    vector<int> cnt;

    segtree(int n){
        sm.assign(4 * n + 4, 0);
        cnt.assign(4 * n + 4, 0);
    }

    void add(int v, int tl, int tr, int l, int r, ll x){
        if(tl > r || l > tr)
            return;
        if(l <= tl && tr <= r){
            cnt[v]++;
            sm[v] += x;
            return;
        }
        int tm = (tl + tr) / 2;
        add(2 * v, tl, tm, l, r, x);
        add(2 * v + 1, tm + 1, tr, l, r, x);
    }

    pair<ll, int> get(int v, int tl, int tr, int i){
        if(tl == tr){
            return {sm[v], cnt[v]};
        }
        int tm = (tl + tr) / 2;
        pair<ll, int> ret;
        if(i <= tm){
            ret = get(2 * v, tl, tm, i);
        }else{
            ret = get(2 * v + 1, tm + 1, tr, i);
        }
        return {ret.F + sm[v], ret.S + cnt[v]};
    }
};

struct query{
    int ind, u, v, g;
    ll s;

    query(){

    }

    query(int _ind, int _u, int _v, int _g, ll _s){
        ind = _ind;
        u = _u;
        v = _v;
        g = _g;
        s = _s;
    }
};

bool cmp(pair<pii, query> a, pair<pii, query> b){
    return a.F < b.F;
}

const int K = 19;

int n, m, q, tin[N], tout[N], tick, U[N], V[N], cntp[N], up[N][K];
ll ans[N];
vector<pair<ll, int>> post;
vector<int> g[N];

void dfs(int v, int p){
    tin[v] = ++tick;
    up[v][0] = p;
    for(int k = 1; k < K; k++)
        up[v][k] = up[up[v][k - 1]][k - 1];
    for(auto u : g[v]){
        if(u == p) continue;
        dfs(u, v);
    }
    tout[v] = tick;
}

void dfs1(int v, int p){
    for(auto u : g[v]){
        if(u == p) continue;
        cntp[u] += cntp[v];
        dfs1(u, v);
    }
}

bool ispar(int p, int v){
    return (tin[p] <= tin[v] && tout[v] <= tout[p]);
}

int lca(int u, int v){
    if(ispar(u, v))
        return u;
    if(ispar(v, u))
        return v;
    for(int k = K - 1; k >= 0; k--){
        if(!ispar(up[u][k], v))
            u = up[u][k];
    }
    return up[u][0];
}

void solve() {
    cin >> n >> m >> q;
    for(int i = 1; i < n; i++){
        cin >> U[i] >> V[i];
        g[U[i]].pb(V[i]);
        g[V[i]].pb(U[i]);
    }
    dfs(1, 1);
    post.push_back({-infi, -1});
    for(int i = 1; i <= m; i++){
        int r, s;
        cin >> r >> s;
        int u = U[r], v = V[r];
        if(tin[u] > tin[v])
            swap(u, v);
        cntp[v]++;
        post.push_back({s, r});
    }
    dfs1(1, 0);
    sort(post.begin(), post.end());
    vector<pair<pair<int, int>, query>> qs;
    for(int i = 1; i <= q; i++){
        int s, t, x;
        ll y;
        cin >> s >> t >> x >> y;
        qs.push_back({{0, m + 1}, query(i, s, t, x, y)});
    }
    for(int lv = 0; lv < 20; lv++){
        segtree tr = segtree(n);
        sort(qs.begin(), qs.end(), cmp);
        vector<pair<pair<int, int>, query>> nqs;
        int cur = 0;
        for(auto e : qs){
            int lo = e.F.F, hi = e.F.S;
            int m = (lo + hi) / 2;
            query q = e.S;
            while(cur < m){
                cur++;
                int u = U[post[cur].S], v = V[post[cur].S];
                if(tin[u] > tin[v])
                    swap(u, v);
                tr.add(1, 1, n, tin[v], tout[v], post[cur].F);
            }
            int lc = lca(q.u, q.v);
            if(tr.get(1, 1, n, tin[q.u]).F + tr.get(1, 1, n, tin[q.v]).F - 2 * tr.get(1, 1, n, tin[lc]).F > q.s){
                nqs.push_back({{lo, m}, q});
            }else{
                nqs.push_back({{m, hi}, q});
                int lft = cntp[q.u] + cntp[q.v] - 2 * cntp[lc];
                lft -= tr.get(1, 1, n, tin[q.u]).S + tr.get(1, 1, n, tin[q.v]).S - 2 * tr.get(1, 1, n, tin[lc]).S;
                ans[q.ind] = q.g - lft;
            }
        }
        qs.swap(nqs);
    }
    for(int i = 1; i <= q; i++){
        cout << (ans[i] < 0 ? -1 : ans[i]) << '\n';
    }
}

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

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