Submission #991117

#	Time	Username	Problem	Language	Result	Execution time	Memory
991117		ThMinh_	Two Currencies (JOI23_currencies)	C++17	40 / 100	647 ms	210044 KiB

currencies

#include<bits/stdc++.h>
#define forin(i,a,b) for(int i=a;i<=b;++i)
#define forde(i,a,b) for(int i=a;i>=b;--i)
#define ll long long
using namespace std;
const int N = 1e5 + 10;
int n, m, q, it;
int road[N << 1], st[N], ed[N], h[N], par[17][N];
vector<int> adj[N], gin[N];
pair<int, int> e[N];
void dfs(int u) {
    road[++it] = u;
    st[u] = it;
    for(auto v : adj[u]) if(v != par[0][u]) {
        h[v] = h[u] + 1;
        par[0][v] = u;
        forin(i,1,log2(n)) par[i][v] = par[i - 1][par[i - 1][v]];
        dfs(v);
    }
    road[++it] = u;
    ed[u] = it;
}
int lca(int x, int y) {
    if(h[x] < h[y]) swap(x, y);
    int delta = h[x] - h[y];
    forin(i,0,log2(n)) if((delta >> i) & 1) {
        x = par[i][x];
    }
    if(x == y) return x;
    forde(i,log2(n),0) if(par[i][x] != par[i][y]) {
        x = par[i][x];
        y = par[i][y];
    }
    return par[0][x];
}
int child(int p, int x) {
    int delta = h[x] - h[p] - 1;
    if(delta == -1) return st[p];
    forin(i,0,log2(n)) if((delta >> i) & 1) {
        x = par[i][x];
    }
    return st[x] - 1;
}
struct Tree {
    int cnt;
    ll sum;
    Tree* lf;
    Tree* rt;
    Tree () : sum(), cnt(), lf(), rt() { }
};
ll sum(Tree* id) {
    return id ? id -> sum : 0;
}
int cnt(Tree* id) {
    return id ? id -> cnt : 0;
}
void up(Tree* id, int f, int l, int i, int val1, int val2) {
    if(f == l) {
        id -> sum += val1;
        id -> cnt += val2;
        return;
    }
    int mid = f + l >> 1;
    if(i <= mid) {
        id -> lf = id -> lf ? new Tree(*id -> lf) : new Tree();
        up(id -> lf, f, mid, i, val1, val2);
    }
    else {
        id -> rt = id -> rt ? new Tree(*id -> rt) : new Tree();
        up(id -> rt, mid + 1, l, i, val1, val2);
    }
    id -> sum = sum(id -> lf) + sum(id -> rt);
    id -> cnt = cnt(id -> lf) + cnt(id -> rt);
}
vector<int> vt;
int get(Tree* fu, Tree* lu, Tree* fv, Tree* lv, int f, int l, ll val) {
    if(f == l) {
        int dd = val / vt[f - 1];
        int gold = cnt(lu) - cnt(fu) + cnt(lv) - cnt(fv);
        return max(0, gold - dd);
    }
    int mid = f + l >> 1;
    ll silver = sum(lu -> lf) - sum(fu -> lf) + sum(lv -> lf) - sum(fv -> lf);
    if(silver >= val) {
        if(!fu -> lf) fu -> lf = new Tree(); if(!lu -> lf) lu -> lf = new Tree();
        if(!fv -> lf) fv -> lf = new Tree(); if(!lv -> lf) lv -> lf = new Tree();
        int gold = cnt(lu -> rt) - cnt(fu -> rt) + cnt(lv -> rt) - cnt(fv -> rt);
        return get(fu -> lf, lu -> lf, fv -> lf, lv -> lf, f, mid, val) + gold;
    }
    else {
        if(!fu -> rt) fu -> rt = new Tree(); if(!lu -> rt) lu -> rt = new Tree();
        if(!fv -> rt) fv -> rt = new Tree(); if(!lv -> rt) lv -> rt = new Tree();
        return get(fu -> rt, lu -> rt, fv -> rt, lv -> rt, mid + 1, l, val - silver);
    }
}
int32_t main () {
    cin.tie(0)->sync_with_stdio(0);
    if(fopen("Task.inp","r")) {
        freopen("Task.inp","r",stdin);
        freopen("WA.out","w",stdout);
    }
    cin>>n>>m>>q;
    forin(i,1,n - 1) {
        int u, v; cin>>u>>v;
        adj[u].push_back(v);
        adj[v].push_back(u);
        e[i] = {u, v};
    }
    dfs(1);
    while(m--) {
        int r; ll c; cin>>r>>c;
        int u, v; tie(u, v) = e[r];
        if(h[u] < h[v]) swap(u, v);
        gin[u].push_back(c);
        vt.push_back(c);
    }
    sort(vt.begin(), vt.end());
    vt.resize(unique(vt.begin(), vt.end()) - vt.begin());
    int mx = vt.size();
    vector<Tree*> tr;
    tr.resize(it + 1);
    tr[0] = new Tree();
    forin(i,1,it) {
        int u = road[i];
        tr[i] = new Tree(*tr[i - 1]);
        if(i == st[u]) for(auto c : gin[u]) {
            int pos = upper_bound(vt.begin(), vt.end(), c) - vt.begin();
            up(tr[i], 1, mx, pos, c, 1);
        }
        if(i == ed[u]) for(auto c : gin[u]) {
            int pos = upper_bound(vt.begin(), vt.end(), c) - vt.begin();
            up(tr[i], 1, mx, pos, -c, -1);
        }
    }
    while(q--) {
        int s, t, x; ll y; cin>>s>>t>>x>>y;
        if(st[s] > st[t]) swap(s, t);
        int p = lca(s, t);
        int u = child(p, s);
        int v = child(p, t);
        int ans = get(tr[u], tr[st[s]], tr[v], tr[st[t]], 1, mx, y);
        if(ans > x) cout<<"-1\n";
        else cout<<x - ans<<"\n";
    }
}

Compilation message (stderr)

currencies.cpp: In constructor 'Tree::Tree()':
currencies.cpp:46:8: warning: 'Tree::sum' will be initialized after [-Wreorder]
   46 |     ll sum;
      |        ^~~
currencies.cpp:45:9: warning:   'int Tree::cnt' [-Wreorder]
   45 |     int cnt;
      |         ^~~
currencies.cpp:49:5: warning:   when initialized here [-Wreorder]
   49 |     Tree () : sum(), cnt(), lf(), rt() { }
      |     ^~~~
currencies.cpp: In function 'void up(Tree*, int, int, int, int, int)':
currencies.cpp:63:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   63 |     int mid = f + l >> 1;
      |               ~~^~~
currencies.cpp: In function 'int get(Tree*, Tree*, Tree*, Tree*, int, int, long long int)':
currencies.cpp:82:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   82 |     int mid = f + l >> 1;
      |               ~~^~~
currencies.cpp:85:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   85 |         if(!fu -> lf) fu -> lf = new Tree(); if(!lu -> lf) lu -> lf = new Tree();
      |         ^~
currencies.cpp:85:46: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   85 |         if(!fu -> lf) fu -> lf = new Tree(); if(!lu -> lf) lu -> lf = new Tree();
      |                                              ^~
currencies.cpp:86:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   86 |         if(!fv -> lf) fv -> lf = new Tree(); if(!lv -> lf) lv -> lf = new Tree();
      |         ^~
currencies.cpp:86:46: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   86 |         if(!fv -> lf) fv -> lf = new Tree(); if(!lv -> lf) lv -> lf = new Tree();
      |                                              ^~
currencies.cpp:91:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   91 |         if(!fu -> rt) fu -> rt = new Tree(); if(!lu -> rt) lu -> rt = new Tree();
      |         ^~
currencies.cpp:91:46: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   91 |         if(!fu -> rt) fu -> rt = new Tree(); if(!lu -> rt) lu -> rt = new Tree();
      |                                              ^~
currencies.cpp:92:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   92 |         if(!fv -> rt) fv -> rt = new Tree(); if(!lv -> rt) lv -> rt = new Tree();
      |         ^~
currencies.cpp:92:46: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   92 |         if(!fv -> rt) fv -> rt = new Tree(); if(!lv -> rt) lv -> rt = new Tree();
      |                                              ^~
currencies.cpp: In function 'int32_t main()':
currencies.cpp:99:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   99 |         freopen("Task.inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
currencies.cpp:100:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  100 |         freopen("WA.out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~

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