제출 #1257632

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1257632		shafi_root	Two Currencies (JOI23_currencies)	C++20	0 / 100	5 ms	5704 KiB

currencies

/* _In The Name Of God_ */

#include <bits/stdc++.h>
using namespace std;

#define maxs(a, b)			a = max(a, b)
#define mins(a, b)			a = min(a, b)
#define pb						push_back
#define F						first
#define S						second
#define lc						id << 1
#define rc						lc|1
#define mid						((l + r)/2)
// #define int                     long long

typedef pair<int, int>     	pii;
typedef long long               	ll;

const ll  MOD    = 1e9  + 7; // 998244353;
const ll  INF    = 1e9  + 1;
const int MXN    = 1e5  + 5;
const int LOG    = 18;

ll Pow(ll a, ll b) { return !b ? 1 : (Pow(a*a %MOD, b/2) * (b&1 ? a : 1)) %MOD; }

int n, m, q, L[MXN], R[MXN], M[MXN], X[MXN], Y[MXN], s[MXN], t[MXN],
 num[MXN], h[MXN], st[MXN], fn[MXN], cnt[MXN], timer=1, sum, par[LOG][MXN], val[MXN], Ans[MXN];
ll fen[MXN];
pii E[MXN];
vector<int> adj[MXN], Que[MXN];
vector<pii> vec;

void dfs(int v, int p) {
    val[v] = sum;
    h[v] = h[p] + (v!=p);
    st[v] = timer++;
    par[0][v] = p;
    for (int i = 1; i < LOG; i++) {
        par[i][v] = par[i-1][par[i-1][v]];
    }
    for (int x : adj[v]) {
        int u = E[x].F ^ E[x].S ^ v;
        if (u != p) {
            sum += cnt[x];
            dfs(u, v);
            sum -= cnt[x];
        }
    }
    fn[v] = timer;
}

int jump(int v, int k) {
    for (int i = 0; i < LOG; i++) {
        if (k >> i & 1) v = par[i][v];
    }
    return v;
}

int LCA(int u, int v) {
    if (h[u] < h[v]) swap(u, v);
    u = jump(u, h[u] - h[v]);
    if (u == v) return u;
    for (int i = LOG-1; i >= 0; i--) {
        if (par[i][u] != par[i][v]) u = par[i][u], v = par[i][v];
    }
    return par[0][u];
}

void upd(int p, int x) {
    for (; p < n+3; p += p &- p) {
        fen[p] += x;
    }
    // fen[p]+=x;
}

ll get(int p) {
    ll res = 0;
    for (; p; p -= p &- p) {
        res += fen[p];
    }
    // for (int i = 1; i <= p; i++) res += fen[i];
    return res;
}

void Solve() {
    fill(fen, fen + n+3, 0);
    for (int i = 0; i < m; i++) {
        int p = h[E[vec[i].S].F] > h[E[vec[i].S].S] ? E[vec[i].S].F : E[vec[i].S].S;
        upd(st[p], vec[i].F);
        upd(fn[p], -vec[i].F);
        for (int qr : Que[i]) {
            ll ans = get(st[s[qr]]) + get(st[t[qr]]) - 2ll*get(st[LCA(s[qr], t[qr])]);
            if (ans <= X[qr]) L[qr] = i;
            else R[qr] = i;
        }
    }
}

void Sol() {
    fill(fen, fen + n+3, 0);
    for (int i = 0; i < m; i++) {
        int p = h[E[vec[i].S].F] > h[E[vec[i].S].S] ? E[vec[i].S].F : E[vec[i].S].S;
        upd(st[p], 1);
        upd(fn[p], -1);
        for (int qr : Que[i]) {
            ll ans = get(st[s[qr]]) + get(st[t[qr]]) - 2ll*get(st[LCA(s[qr], t[qr])]);
            Ans[qr] = num[qr] - ans;
        }
    }
}

void _solve() {
    cin >> n >> m >> q;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        E[i].F = u, E[i].S = v;
        adj[u].pb(i);
        adj[v].pb(i);
    }
    for (int i = 1; i <= m; i++) {
        int v, c;
        cin >> v >> c;
        vec.pb({c, v});
        cnt[v]++;
    }
    dfs(1, 1);
    sort(vec.begin(), vec.end());
    for (int i = 1; i <= q; i++) {
        cin >> s[i] >> t[i] >> Y[i] >> X[i];
        num[i] = val[s[i]] + val[t[i]] - 2*val[LCA(s[i], t[i])];
        L[i] = -1, R[i] = m; // L[i]+1 silver, if we can L[i] = mid
    }
    for (int step = 0; step < LOG; step++) {
        for (int i = 0; i <= m; i++) Que[i].clear();
        for (int i = 1; i <= q; i++) Que[(L[i]+R[i])/2].pb(i);
        Solve();
    }
    for (int i = 0; i <= m; i++) Que[i].clear();
    for (int i = 1; i <= q; i++) {
        if (L[i] != -1) Que[L[i]].pb(i);
        else {
            Ans[i] = num[i];
        }
    }
    Sol();
    for (int i = 1; i <= q; i++) {
        cout << max(-1, Y[i] - Ans[i]) << '\n';
    }
}

int32_t main() {
    cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
    int _ = 1;
    // cin >> _;
    while (_--) _solve();
    return 0.0;
}

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