Submission #759337

#	Time	Username	Problem	Language	Result	Execution time	Memory
759337		raysh07	Two Currencies (JOI23_currencies)	C++17	100 / 100	1963 ms	67944 KiB

currencies

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF (int)1e18
#define f first
#define s second

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

struct query{
    int a, b, lc, gold, silver, need, l, r, i;
};

struct check{
    int a, c;
};

int n, m, q;
const int N = 1e5 + 69;
vector <int> adj[N], work[N];
int seg[4 * N], lazy[4 * N], dep[N], lift[N][20], tin[N], tout[N], timer = 0;
query Q[N];
check C[N];

void dfs(int u, int par){
    tin[u] = ++timer;
    for (int v : adj[u]){
        if (v == par) continue;
        lift[v][0] = u;
        dep[v] = dep[u] + 1;
        dfs(v, u);
    }
    
    tout[u] = timer;
}

int findlca(int a, int b){
    if (dep[a] < dep[b]) swap(a, b);
    int del = dep[a] - dep[b];
    for (int i = 0; i < 20; i++) if (del >> i & 1) a = lift[a][i];
    if (a == b) return a;
    for (int i = 19; i >= 0; i--) if (lift[a][i] != lift[b][i]){
        a = lift[a][i];
        b = lift[b][i];
    }
    return lift[a][0];
}

void updlazy(int l, int r, int pos){
    seg[pos] += lazy[pos] * (r - l + 1);
    if (l == r){
        lazy[pos] = 0;
        return;
    }
    
    lazy[pos * 2] += lazy[pos];
    lazy[pos * 2 + 1] += lazy[pos];
    lazy[pos] = 0;
    return;
}

void upd(int l, int r, int pos, int ql, int qr, int v){
    if (lazy[pos] != 0) updlazy(l, r, pos);
    if (l >= ql && r <= qr){
        seg[pos] += (r - l + 1) * v;
        if (l == r) return;
        lazy[pos * 2] += v;
        lazy[pos * 2 + 1] += v;
    } 
    else if (l > qr || r < ql) return;
    else {
        int mid = (l + r)/2;
        upd(l, mid, pos*2, ql, qr, v);
        upd(mid + 1, r, pos*2 + 1, ql, qr, v);
        
        seg[pos] = seg[pos * 2] + seg[pos * 2 + 1];
    }
}

int query(int l, int r, int pos, int qp){
    if (lazy[pos] != 0) updlazy(l, r, pos);
    if (l == r) return seg[pos];
    
    int mid = (l + r)/2;
    if (qp <= mid) return query(l, mid, pos*2, qp);
    else return query(mid + 1, r, pos*2 + 1, qp);
}

int querypath(int a, int b, int lc){
    return query(1, n, 1, tin[a]) + query(1, n, 1, tin[b]) - 2 * query(1, n, 1, tin[lc]);
}

void pbs(){
    for (int i = 1; i <= m; i++) work[i].clear();
    for (int i = 1; i <= 4 * n; i++) seg[i] = lazy[i] = 0;
    
    for (int i = 1; i <= q; i++){
        if (Q[i].l == Q[i].r) continue;
        int m = (Q[i].l + Q[i].r + 1)/2;
        work[m].push_back(i);
    }
    
    for (int i = 1; i <= m; i++){
        upd(1, n, 1, tin[C[i].a], tout[C[i].a], C[i].c);
        
        for (auto x : work[i]){
            int val = querypath(Q[x].a, Q[x].b, Q[x].lc);
            if (val > Q[x].silver) Q[x].r = i - 1;
            else Q[x].l = i;
        }
    }
}

bool comp(check a, check b){
    return a.c < b.c;
}

void Solve() 
{
    cin >> n >> m >> q;
    
    vector <pair<int, int>> e;
    
    for (int i = 1; i < n; i++){
        int u, v; cin >> u >> v;
        
        adj[u].push_back(v);
        adj[v].push_back(u);
        e.push_back({u, v});
    }
    
    dfs(1, -1);
    for (int j = 1; j < 20; j++) for (int i = 1; i <= n; i++) lift[i][j] = lift[lift[i][j - 1]][j - 1];
    
    for (int i = 1; i <= m; i++){
        int p, c; cin >> p >> c;
        --p;
        if (dep[e[p].f] > dep[e[p].s]) C[i].a = e[p].f;
        else C[i].a = e[p].s;
        C[i].c = c;
    }
    
    sort(C + 1, C + m + 1, comp);
    
    for (int i = 1; i <= q; i++){
        int a, b, x, y; cin >> a >> b >> x >> y;
        
        Q[i].a = a;
        Q[i].b = b;
        Q[i].gold = x;
        Q[i].silver = y;
        Q[i].i = i;
        Q[i].lc = findlca(a, b);
        Q[i].l = 0;
        Q[i].r = m;
    }
    
    for (int it = 0; it < 20; it++){
        pbs();
    }
    
    for (int i = 1; i <= m; i++) work[i].clear();
    for (int i = 1; i <= 4 * n; i++) seg[i] = lazy[i] = 0;
    
    for (int i = 1; i <= q; i++){
        assert(Q[i].l == Q[i].r);
        
        if (Q[i].l == m){
            Q[i].need = 0;
        } else {
            work[Q[i].l + 1].push_back(i);
        }
    }
    
    for (int i = m; i >= 1; i--){
        upd(1, n, 1, tin[C[i].a], tout[C[i].a], 1);
        
        for (auto x : work[i]){
            Q[x].need = querypath(Q[x].a, Q[x].b, Q[x].lc);
        }
    }
    
    for (int i = 1; i <= q; i++){
        int x = i;
        if (Q[x].need > Q[x].gold) cout << "-1\n";
        else cout << Q[x].gold - Q[x].need << "\n";
    }
}

int32_t main() 
{
    auto begin = std::chrono::high_resolution_clock::now();
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
 //   cin >> t;
    for(int i = 1; i <= t; i++) 
    {
        //cout << "Case #" << i << ": ";
        Solve();
    }
    auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
    return 0;
}

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