Submission #736712

#	Time	Username	Problem	Language	Result	Execution time	Memory
736712		Cookie	Two Currencies (JOI23_currencies)	C++14	68 / 100	5039 ms	102032 KiB

currencies

#include<bits/stdc++.h>
#include<fstream>
using namespace std;
ifstream fin("WINTER.inp");
ofstream fout("WINTER.out");
#define int long long
#define ll long long
#define pb push_back
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define ld long double
#define vt vector
#include<fstream>
#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>
const ld PI = 3.14159265359;
const int x[4] = {1, -1, 0, 0};
const int y[4] = {0, 0, 1, -1};
const ll mod = 1e9 + 7;
const int mxn = 2e5, mxm = 1e5, sq = 400;
const int base = (1 << 18);
const ll inf = 1e9;
const ld pre = 1e-6;
struct Qu{
    int s, t, x, y, id;
};

vt<pii>edge, weight;

vt<Qu>qq;
int n, m, q;
vt<pii>adj[mxn + 1];
int ans[mxn + 1], tin[mxn + 1], tout[mxn + 1], dep[mxn + 1], up[mxn + 1][17], tt = 0;
ll dep2[mxn + 1], cnt2[mxn + 1], w[mxn + 1];

struct ST{
    ll st[4 * mxn + 1], lz[4 * mxn + 1];
    void push(int nd, int l, int mid, int r){
        st[nd << 1] += (mid - l + 1) * lz[nd]; lz[nd << 1] += lz[nd];
        st[nd << 1 | 1] += (r - mid) * lz[nd]; lz[nd << 1 | 1] += lz[nd];
        lz[nd] = 0;
    }
    void upd(int nd, int l, int r, int ql, int qr, ll v){
        if(ql > r || qr < l)return;
        if(ql <= l && qr >= r){
            st[nd] += 1LL * (r - l + 1) * v; lz[nd] += v;
            return;
        }
        int mid = (l + r) >> 1;
        push(nd, l, mid, r);
        upd(nd << 1, l, mid, ql, qr, v); upd(nd << 1 | 1, mid + 1, r, ql, qr, v);
        st[nd] = st[nd << 1] + st[nd << 1 | 1];
    }
    ll get(int nd, int l, int r, int ql, int qr){
        if(ql > r || qr < l)return(0);
        
        if(ql <= l && qr >= r){
            
            return(st[nd]);
        }
        int mid = (l + r) >> 1;
        push(nd, l, mid, r);
        return(get(nd << 1, l, mid, ql, qr) + get(nd << 1 | 1, mid + 1, r, ql, qr));
    }
    ll single(int x){
        
        return(get(1, 1, n, x, x));
    }
    void update(int u, ll v){
        upd(1, 1, n, tin[u], tout[u], v);
    }
};
ST cnt, sm;
int lca(int a, int b){
    if(dep[a] < dep[b])swap(a, b);
    int k = dep[a] - dep[b];
    forr(i, 0, 17){
        if(k & (1 << i)){
            a = up[a][i];
        }
    }
    if(a == b)return(a);
    for(int i = 16; i >= 0; i--){
        if(up[a][i] != up[b][i]){
            a = up[a][i]; b = up[b][i];
        }
    }
    return(up[a][0]);
}
void solve(int l, int r, vt<Qu>cand){
    if(l > r || cand.empty())return;
    int mid = (l + r) >> 1;
    for(int i = l; i <= mid; i++){
        int id = weight[i].se, u;
        if(dep[edge[id].fi] > dep[edge[id].se])u = edge[id].fi;
        else u = edge[id].se;
        
        sm.update(u, weight[i].fi);
        
        cnt.update(u, 1);
    }
    vt<Qu>yes, no;
    for(auto [s, t, x, y, id]: cand){
        ll w = sm.single(tin[s]) + sm.single(tin[t]) - 2 * sm.single(tin[lca(s, t)]);
        int countt = cnt.single(tin[s]) + cnt.single(tin[t]) - 2 * cnt.single(tin[lca(s, t)]);
        
        if(w <= y){
            
            y -= w;
            ans[id] += countt;
            yes.pb({s, t, x, y, id});
        }else{
            no.pb({s, t, x, y, id});
        }
    }
    for(int i = l; i <= mid; i++){
        int id = weight[i].se, u;
        if(dep[edge[id].fi] > dep[edge[id].se])u = edge[id].fi;
        else u = edge[id].se;
        sm.update(u, -weight[i].fi);
        cnt.update(u, -1);
    }
    solve(l, mid - 1, no); solve(mid + 1, r, yes);
}
void dfs(int s, int pre){
    tin[s] = ++tt;
    for(auto [i, id]: adj[s]){
        if(i != pre){
            dep2[i] = dep2[s] + cnt2[id];
            up[i][0] = s; dep[i] = dep[s] + 1;
            dfs(i, s);
        }
    }
    tout[s] = tt;
}
signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> m >> q;
    edge.resize(n + 1);
    forr(i, 1, n){
        int u, v; cin >> u >> v;
        edge[i] = {u, v};
        adj[u].pb({v, i}); adj[v].pb({u, i});
    }
    forr(i, 0, m){
        int p, c; cin >> p >> c;
        weight.pb({c, p});
        cnt2[p]++;
    }
    
    sort(weight.begin(), weight.end());
    dfs(1, -1);
    for(int i = 1; i < 17; i++){
        for(int j= 1; j <= n; j++){
            up[j][i] = up[up[j][i - 1]][i - 1];
        }
    }
    forr(i, 0, q){
        int s, t, x, y; cin >> s >> t >> x >> y;
        qq.pb({s, t, x, y, i});
    }
    solve(0, weight.size() - 1, qq);
    
    forr(i, 0, q){
        //cout << ans[i] << " ";
        auto [s, t, x, y, id] = qq[i];
        int len = dep2[s] + dep2[t] - 2 * dep2[lca(s, t)];
        //cout << len << " ";
        if(len - ans[i] <= x){
            cout << x - (len - ans[i]) << "\n";
        }else{
            cout << -1 << "\n";
        }
    }
    return(0);
}

Compilation message (stderr)

currencies.cpp: In function 'void solve(long long int, long long int, std::vector<Qu>)':
currencies.cpp:105:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  105 |     for(auto [s, t, x, y, id]: cand){
      |              ^
currencies.cpp: In function 'void dfs(long long int, long long int)':
currencies.cpp:129:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  129 |     for(auto [i, id]: adj[s]){
      |              ^
currencies.cpp: In function 'int main()':
currencies.cpp:168:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  168 |         auto [s, t, x, y, id] = qq[i];
      |              ^

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