Submission #1046818

#	Time	Username	Problem	Language	Result	Execution time	Memory
1046818		He_Huanglu	Two Currencies (JOI23_currencies)	C++17	0 / 100	4 ms	15196 KiB

currencies

#include <bits/stdc++.h>
#define ii pair<int, int>
#define fi first 
#define se second 
using namespace std;

const int N = 1e5 + 5, S = 17;
ii adj[N], p[N], range[N];
vector <int> ke[N], lst[N], gido[N];
struct date{
    int u, v, gol, sil;
} t[N];
int n, m, q, d[N], par[N][S], timer, st[N], ed[N], bit[N], cnt[N], ans[N], s[N];

void dfs(int u, int pre = 0) {
    d[u] = d[pre] + 1;
    par[u][0] = pre;
    for(int i = 1; i < S; i++) {
        par[u][i] = par[par[u][i - 1]][i - 1];
    }
    st[u] = ++timer;
    for(int v : ke[u]) if(v != par[u][0]) dfs(v, u);
    ed[u] = timer;

}

void upd_point(int x, int u, int v) {
    while (x <= n) {
        bit[x] += u; // coin
        cnt[x] += v;
        x += (x & (-x));
    }
}

void upd_range(int l, int r, int u, int v) {
    upd_point(l, u, v);
    upd_point(r + 1, -u, -v);
}

void upd_adj(int id) {
    int x, coin; x = p[id].se, coin = p[id].fi;
    int u, v; u = adj[x].fi, v = adj[x].se;
    if(d[u] > d[v]) swap(u, v);
//cout << v << " " << st[v] << " " << ed[v] << " " << coin << "^^\n";
    upd_range(st[v], ed[v], coin, 1);
}

int lca(int u, int v) {
    if(d[u] > d[v]) swap(u, v);
    int dist = d[v] - d[u];
    for(int i = S - 1; i >= 0; i--) if((dist >> i) & 1) {
        v = par[v][i];
    }
    if(u == v) return u;
    for(int i = S - 1; i >= 0; i--) if(par[u][i] != par[v][i]) {
        u = par[u][i], v = par[v][i];
    }
    return par[u][0];
}

int get_s(int x) {
    int ret = 0; x = st[x];
    while (x > 0) {
        ret += bit[x];
        x -= (x & (-x));
    }
    return ret;
}

int get_g(int x) {
    int ret = 0; x = st[x];
    while (x > 0) {
        ret += cnt[x];
        x -= (x & (-x));
    }
    return ret;
}

int check(int i, int id) {
    int u = t[i].u, v = t[i].v, gol = t[i].gol, sil = t[i].sil;
    int o = lca(u, v);
    int silver = get_s(u) + get_s(v) - 2 * get_s(o);
    int gg = get_g(u) + get_g(v) - 2 * get_g(o);
    int gold = s[u] + s[v] - 2 * s[o] - gg;
    if(silver <= t[i].sil) return gold;
    return -1;
}

void dfs2(int u) {
    for(int v : ke[u]) if(v != par[u][0]) {
        s[v] += s[u];
        dfs2(v);
    }
}


int main () {
    // input
    cin >> n >> m >> q;
    for(int i = 1; i < n; i++) {
        int u, v; cin >> u >> v;
        adj[i] = make_pair(u, v);
        ke[u].push_back(v);
        ke[v].push_back(u);
    }
    for(int i = 1; i <= m; i++) {
        cin >> p[i].se >> p[i].fi;
    }
    for(int i = 1; i <= q; i++) {
        cin >> t[i].u >> t[i].v >> t[i].gol >> t[i].sil;
    }
    // xuli
    for(int i = 1; i <= q; i++) ans[i] = 1e9;
    sort(p + 1, p + 1 + m); 
    dfs(1);
    int lim = ceil(1.0 * log2(m + 1)) + 1; int mid_f = m / 2;
    for(int i = 1; i <= m; i++) {
        int x = p[i].se;
        int u = adj[x].fi, v = adj[x].se;
        if(d[u] > d[v]) swap(u, v);
        s[v]++; 
    }
    dfs2(1);
    for(int i = 1; i <= q; i++) {
        range[i] = make_pair(0, n);
        lst[mid_f].push_back(i);
    }
    // solve
    for(int turn = 1; turn <= lim; turn++) {
        for(int i = 1; i <= n; i++) bit[i] = cnt[i] = 0;
        for(int id = 0; id <= m; id++) {
            if(id) upd_adj(id); 
            for(int i : lst[id]) {               
                int ok = check(i, id);
                if(ok >= 0) {
                    range[i].fi = id + 1;
                    ans[i] = min(ans[i], ok); 
                }
                else range[i].se = id - 1;
                int mid = (range[i].fi + range[i].se) >> 1;
                gido[mid].push_back(i);
            }
            lst[id].clear();
        }
        for(int id = 0; id <= m; id++) {
            while (gido[id].size()) {
                lst[id].push_back(gido[id].back());
                gido[id].pop_back();
            }
        }
    }
    // output
    for(int i = 1; i <= q; i++) {
        int res = t[i].gol - ans[i];
        cout << (res < 0 ? -1 : res) << "\n";
    }
}

Compilation message (stderr)

currencies.cpp: In function 'int check(int, int)':
currencies.cpp:80:33: warning: unused variable 'gol' [-Wunused-variable]
   80 |     int u = t[i].u, v = t[i].v, gol = t[i].gol, sil = t[i].sil;
      |                                 ^~~
currencies.cpp:80:49: warning: unused variable 'sil' [-Wunused-variable]
   80 |     int u = t[i].u, v = t[i].v, gol = t[i].gol, sil = t[i].sil;
      |                                                 ^~~

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