Submission #932550

#	Time	Username	Problem	Language	Result	Execution time	Memory
932550		Amirreza_Fakhri	Two Currencies (JOI23_currencies)	C++17	40 / 100	5095 ms	67852 KiB

currencies

// In the name of the God
#include <bits/stdc++.h>
#define ll long long
#define int long long
#define pb push_back
#define F first
#define S second
#define mp make_pair
#define pii pair <int, int>
#define smin(x, y) (x) = min((x), (y))
#define smax(x, y) (x) = max((x), (y))
#define all(x) (x).begin(), (x).end()
using namespace std;

const int inf = 1e9+7;
const int mod = 998244353;
const int maxn = 1e5+5, lg = 17, sq = 1000;

struct Q {
    int s, t, x, y, cnt = 0;
} qs[maxn];

int n, m, q, ti = 0, fr[maxn], to[maxn], in[maxn], out[maxn], h[maxn];
int mark[maxn], mark2[maxn];
pair <int, pii> par[lg][maxn];
vector <int> adj[maxn], handle;
vector <pii> ch;

void dfs1(int v = 0, int p = 0) {
    in[v] = ti++;
    for (int u : adj[v]) {
        if (u != p) {
            h[u] = h[v]+1; dfs1(u, v);
        }
    }
    out[v] = ti;
}

void dfs2(int v = 0, int p = 0) {
    par[0][v].F = p;
    for (int i = 1; i < lg; i++) {
        int u = par[i-1][v].F;
        par[i][v] = mp(par[i-1][u].F,
            mp(par[i-1][v].S.F+par[i-1][u].S.F, par[i-1][v].S.S+par[i-1][u].S.S));
    }
    for (int u : adj[v]) {
        if (u != p) dfs2(u, v);
    }
}

pii lca(int v, int u) {
    pii res(0, 0);
    if (h[v] < h[u]) swap(v, u);
    int d = h[v]-h[u];
    for (int i = 0; i < lg; i++) {
        if (d&(1<<i)) {
            res.F += par[i][v].S.F, res.S += par[i][v].S.S;
            v = par[i][v].F;
        }
    }
    if (v == u) return res;
    for (int i = lg-1; i >= 0; i--) {
        if (par[i][v].F != par[i][u].F) {
            res.F += par[i][v].S.F+par[i][u].S.F, res.S += par[i][v].S.S+par[i][u].S.S;
            v = par[i][v].F, u = par[i][u].F;
        }
    }
    res.F += par[0][v].S.F+par[0][u].S.F, res.S += par[0][v].S.S+par[0][u].S.S;
    return res;
}

bool is (int v, int u) {
    return in[v] <= in[u] and out[v] >= out[u];
}

int32_t main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> m >> q;
    for (int i = 0; i < n-1; i++) {
        cin >> fr[i] >> to[i];
        adj[--fr[i]].pb(--to[i]);
        adj[to[i]].pb(fr[i]);
    }
    dfs1();
    for (int i = 0; i < m; i++) {
        int p, c; cin >> p >> c;
        p--;
        int v = fr[p];
        if (in[v] < in[to[p]]) v = to[p];
        ch.pb(mp(c, v));
    }
    for (int i = 0; i < q; i++) {
        cin >> qs[i].s >> qs[i].t >> qs[i].x >> qs[i].y;
        qs[i].s--, qs[i].t--;
    }
    sort(all(ch));
    for (int i = 0; i < m; i++) {
        par[0][ch[i].S].S.F++, par[0][ch[i].S].S.S += ch[i].F;
        if (i != m-1 and (i%sq ) != (sq-1)) continue;
        dfs2();
        for (int j = 0; j < q; j++) {
            if (mark[j]) continue;
            pii p = lca(qs[j].s, qs[j].t);
            if (p.S >= qs[j].y) {
                handle.pb(j); mark[j] = 1;
            }
            else qs[j].y -= p.S, qs[j].cnt += p.F;            
        }
        for (int j = (i/sq)*sq; j <= i; j++) {
            assert(j-i+1 <= sq);
            int v = ch[j].S, w = ch[j].F;
            for (int k : handle) {
                if (is(v, qs[k].s) != is(v, qs[k].t)) {
                    if (w <= qs[k].y) qs[k].y -= w, qs[k].cnt++;
                }
            }
        }
        handle.clear();
        for (int j = 0; j < n; j++) par[0][j].S = mp(0, 0);
    }
    for (int i = 0; i < m; i++) par[0][ch[i].S].S.F++, par[0][ch[i].S].S.S += ch[i].F;
    dfs2();
    for (int i = 0; i < q; i++) {
        int res = lca(qs[i].s, qs[i].t).F-qs[i].cnt;
        if (res <= qs[i].x) cout << qs[i].x-res << '\n';
        else cout << -1 << '\n';
    }
    return 0;
}

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