Submission #793292

#	Time	Username	Problem	Language	Result	Execution time	Memory
793292		phoenix	Two Currencies (JOI23_currencies)	C++17	100 / 100	1494 ms	39564 KiB

currencies

#include<bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 1e5 + 10;
const int M = (1 << 18);

ll t[2 * M];

void update(int ql, int qr, ll add) {
    for(ql += M, qr += M + 1; ql < qr; ql >>= 1, qr >>= 1) {
        if(ql & 1) t[ql++] += add;
        if(qr & 1) t[--qr] += add;    
    }
}
ll get(int pos) {
    ll res = 0;
    for(pos += M; pos; pos >>= 1) 
        res += t[pos];
    return res;
}


struct edge {
    int u, v, i;
};
struct query {
    ll i, s, t, x, y;
};

int n, m, q;
vector<edge> edges;
vector<pair<int, int>> checkpoints;
vector<query> queries;

vector<int> g[N];
int tin[N], tout[N], depth[N], anc[N][18], T, cnt[N], fla[N];
void precalc(int s, int p) {
    tin[s] = T++;
    anc[s][0] = p;
    for(int i = 1; i < 18; i++) 
        anc[s][i] = anc[anc[s][i - 1]][i - 1];
    for(int to : g[s]) {
        if(to == p) continue;
        depth[to] = depth[s] + 1;
        precalc(to, s);
    }
    tout[s] = T++;
}
void dfs(int s, int p) {
    cnt[s] = cnt[p] + fla[s];
    for(int to : g[s]) {
        if(to == p) continue;
        dfs(to, s);
    }
}
bool up(int u, int v) {
    return tin[u] <= tin[v] && tout[u] >= tout[v];
}

int lca(int u, int v) {
    if(up(u, v)) return u;
    if(up(v, u)) return v;
    for(int i = 17; i >= 0; i--) {
        if(!up(anc[u][i], v)) 
            u = anc[u][i];
    }
    return anc[u][0];
}
int count(int a, int b) {
    return cnt[a] + cnt[b] - 2 * cnt[lca(a, b)];
}
ll func(int a, int b) {
    return get(tin[a]) + get(tin[b]) - 2 * get(tin[lca(a, b)]);
} 

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin >> n >> m >> q;
    edges.resize(n - 1);
    checkpoints.resize(m + 1);
    queries.resize(q);
    
    vector<int> tl(q), tr(q);
    for(int i = 0; i < n - 1; i++) {
        cin >> edges[i].u >> edges[i].v;
        edges[i].i = i;
        g[edges[i].u].push_back(edges[i].v);
        g[edges[i].v].push_back(edges[i].u);
    }
    precalc(1, 1);
    for(int i = 1; i <= m; i++) {
        cin >> checkpoints[i].first >> checkpoints[i].second;
        auto [u, v, ix] = edges[checkpoints[i].first - 1];
        if(depth[u] > depth[v]) swap(u, v);
        checkpoints[i].first = v;
        fla[v]++;
    }
    sort(checkpoints.begin(), checkpoints.end(), [](pair<int, int> r1, pair<int, int> r2) {
        return (r1.second < r2.second);
    });
    //  -- INPUT END --

    dfs(1, 1);
    for(int i = 0; i < q; i++) {
        cin >> queries[i].s >> queries[i].t >> queries[i].x >> queries[i].y;
        queries[i].i = i;
        tl[i] = 0, tr[i] = m + 1;
    }
    for(int iter = 0; iter < 18; iter++) {
        vector<int> oper[m + 1];
        for(int i = 0; i < q; i++) {
            oper[(tl[i] + tr[i]) / 2].push_back(i);
        }
        for(int i = 0; i <= m; i++) {
            if(i) {auto [v, c] = checkpoints[i]; update(tin[v], tout[v], c); }
            for(int p : oper[i]) {   
                if(func(queries[p].s, queries[p].t) <= queries[p].y) 
                    tl[p] = i;
                else 
                    tr[p] = i;
            }
        }
        // return 0;
        for(int i = 1; i <= m; i++) {
            auto [v, c] = checkpoints[i];
            update(tin[v], tout[v], -c);   
        }
    }
    vector<int> oper[m + 1];
    for(int i = 0; i < q; i++) {
        oper[tl[i]].push_back(i);
    }
    int p = 0;
    vector<int> answers(q);
    for(int i = 0; i <= m; i++) {
        if(i) {auto [v, c] = checkpoints[i]; update(tin[v], tout[v], 1);}   
        for(int p : oper[i]) {
            int ans = queries[p].x - count(queries[p].s, queries[p].t) + func(queries[p].s, queries[p].t);
            answers[p] = (ans < 0 ? -1 : ans);
        }
    }
    for(int c : answers)
        cout << c << '\n';
}

Compilation message (stderr)

currencies.cpp: In function 'int main()':
currencies.cpp:136:9: warning: unused variable 'p' [-Wunused-variable]
  136 |     int p = 0;
      |         ^

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