Submission #949098

#	Time	Username	Problem	Language	Result	Execution time	Memory
949098		weakweakweak	Two Currencies (JOI23_currencies)	C++17	0 / 100	218 ms	9064 KiB

currencies

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

#define pii pair<int,int>
#define fs first
#define sc second
const int N = 110000;

int n, m, q;
int sz[N], l[N], r[N], idnow = 0, head[N], par[N], dep[N] = {0}, mxson[N], pe[N], eto[N]; // pe是連到我頭上的那條邊的編號
vector <pii> e[N], checkpoint;
vector <pii> route[N];

int cnt[N] = {0};

void dfs_sz (int i, int p) {
    par[i] = p, dep[i] = dep[p] + 1, sz[i] = 1;
    mxson[i] = -1;
    for (auto [j, id] : e[i]) {
        if (j == p) continue;
        dfs_sz(j, i);
        sz[i] += sz[j], mxson[i] = j;
    }
    for (auto [j, id] : e[i]) if (j != p and sz[j] > sz[mxson[i]]) mxson[i] = j;
}

void build_hld (int i, int p, int hea) {
    head[i] = hea, l[i] = ++idnow;
    for (auto [j, id] : e[i]) {
        if (j == p) pe[l[i]] = id, eto[id] = l[i];
        if (j == mxson[i]) build_hld(j, i, hea);
    }
    for (auto [j, id] : e[i]) if (j != p and j != mxson[i]) build_hld(j, i, j);
    r[i] = idnow;
return;}

vector <pii> hld (int a, int b) {
    vector <pii> res;
    while (head[a] != head[b]) {
        if (dep[head[a]] > dep[head[b]]) swap(a, b);
        res.push_back({l[head[b]], l[b]});
        b = par[head[b]];
    }
    if (a != b) {
        if (dep[a] > dep[b]) swap(a, b);
        res.push_back({l[a] + 1, l[b]});
    }
return res;}

struct bit {
    int n;
    long long a[510000];
    void init (int nn) {
        n = nn;
        memset(a, 0, (n + 10) * 8);
    }
    void update (int i, int x) { for (; i <= n; i += i & -i) a[i] += x; }
    long long query (int i) {
        if (i > n) i = n;
        long long res = 0;
        for (; i > 0 ; i -= i & -i) res += a[i];
        return res;
    }
    long long query2 (int l, int r) {return query(r) - query(l - 1);}
} bit;

long long wow (int i) {
    long long res = 0;
    for (auto p : route[i]) {
        res += bit.query2(p.fs, p.sc);
        // cout << p.fs << ' ' << p.sc << '\n';
    }
    return res;
}



int main () {
    ios_base ::sync_with_stdio(false);
    cin. tie(0);
    //build tree
    cin >> n >> m >> q;
    for (int i = 1; i < n; i++) {
        int a, b;
        cin >> a >> b;
        e[a] . push_back({b, i});
        e[b] . push_back({a, i});
    }
    //build hld
    dfs_sz (1, 1);
    build_hld(1, 1, 1);

    //input checkpoint
    for (int i = 1; i <= m; i++) {
        int pos, c;
        cin >> pos >> c;
        checkpoint . push_back({c, eto[pos]});
    }
    sort(checkpoint.begin(), checkpoint.end());

    //find ans
    for (int i = 1; i <= q; i++) {
        int s, t, x, y;
        cin >> s >> t >> x >> y;
        route[i] = hld(s, t);
        bit.init(n);
        int now = 0;
        for (int j = 0; j < m; j++) {
            bit.update(checkpoint[j].sc, checkpoint[j].fs);
            if (wow(i) > y and wow(i) != now) x--;
            now = wow(i);
        }
        if (x < 0) x = -1;
        cout << x << '\n';
    }
}

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