Submission #1116610

#	Time	Username	Problem	Language	Result	Execution time	Memory
1116610		hqminhuwu	Two Currencies (JOI23_currencies)	C++14	0 / 100	28 ms	36448 KiB

currencies

#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector <int> vi;
typedef pair <ll,ll> pll;
typedef pair <int,int> pii;
typedef pair <int,pii> piii;

#define forr(_a,_b,_c) for(int _a = (_b); _a <= int (_c); ++_a)
#define ford(_a,_b,_c) for(int _a = (_b) + 1; _a --> int (_c);)
#define forf(_a,_b,_c) for(int _a = (_b); _a < int (_c); ++_a)
#define st first
#define nd second
#define pb push_back
#define mp make_pair
#define all(x) begin(x),end(x)
#define mask(i) (1LL << (i))
#define bit(x, i) (((x) >> (i)) & 1)
#define bp __builtin_popcountll
#define file "test"

template<class X, class Y>
    bool minz(X &x, const Y &y) {
        if (x > y) {
            x = y;
            return true;
        } return false;
    }
template<class X, class Y>
    bool maxz(X &x, const Y &y) {
        if (x < y) {
            x = y;
            return true;
        } return false;
    }

const int N = 5e5 + 5;
const ll oo = (ll) 1e16;
const ll mod = 1e9 + 7; // 998244353;

int n, m, q, u, v, p[N], c[N], x[N], s[N], t[N], ed[N];
ll y[N];
vector <int> tax[N], tmp, a[N];

namespace sub1 {
    bool dfs (int u, int p, int z){
        if (u == z){
            return 1;
        }

        for (int i : a[u]){
            int v = ed[i] ^ u;
            if (v == p) continue;
            if (dfs(v, u, z)){
                for (int w : tax[i]){
                    tmp.pb(w);
                }
                return 1;
            }
        }

        return 0;
    }

    void solve(){
        forr (i, 1, q){
            tmp.clear();
            dfs(s[i], s[i], t[i]);
            
            sort(all(tmp));
            int ans = -1, zz = 0;

            if (x[i] >= tmp.size()){
                ans = x[i] - tmp.size();
            }

            for (int v : tmp){
                y[i] -= v;
                zz++;
                if (y[i] < 0) break;
                if (x[i] >= tmp.size() - zz){
                    ans = x[i] - (tmp.size() - zz);
                }
            }

            cout << ans << "\n";
        }
    }
}

struct BIT{
    ll bit[N];
    void add (int u, ll val){
        if (u <= 0) u = 1;
        for (; u <= n; u += u & -u){
            bit[u] += val;
        }
    }

    void add (int l, int r, ll val){
        add(l, val);
        add(r + 1, -val);
    }

    ll get (int u){
        ll res = 0;
        for (; u; u -= u & -u){
            res += bit[u];
        }
        return res;
    }
} bit1, bit2;

namespace uwu {
    int tin[N], tout[N], cnt, dep[N], up[20][N], g[N], low[N], high[N], id[N], dir[N];
    ll gd[N], sv[N], numgd[N], numsv[N], ans[N];
    vector <int> qq[N];

    void dfs (int u, int p){
        tin[u] = ++cnt;
        for (int i : a[u]){
            int v = ed[i] ^ u;
            if (v == p) continue;
            dir[i] = v;
            dep[v] = dep[u] + 1;
            up[0][v] = u;            
            forr (i, 1, 17){
                up[i][v] = up[i - 1][up[i - 1][v]];
            }
            gd[v] = gd[u];
            sv[v] = sv[u];
            for (int w : tax[i]){
                gd[v]++;
                sv[v] += w;
            }
            dfs(v, u);
        }
        tout[u] = cnt;
    }

    int lca (int u, int v){
        if (dep[u] < dep[v]) swap(u, v);
        int k = dep[u] - dep[v];
        ford (i, 17, 0)
        if (bit(i, k)){
            u = up[i][u];
        }
        if (u == v) swap(u, v);
        ford (i, 17, 0)
        if (up[i][u] != up[i][v]){
            u = up[i][u];
            v = up[i][v];
        }
        return up[0][u];
    }

    void solve(){
        forr (i, 1, m){
            id[i] = i;
        }
        sort(id + 1, id + 1 + m, [&](int &u, int &v){return c[u] < c[v];});
        dfs(1, 1);
        forr (i, 1, q){
            low[i] = 0;
            high[i] = m;
            g[i] = lca(s[i], t[i]);
            numsv[i] = sv[s[i]] + sv[t[i]] - sv[g[i]] - sv[up[0][g[i]]];
            numgd[i] = gd[s[i]] + gd[t[i]] - gd[g[i]] - gd[up[0][g[i]]];
        }

        int flag = 1;

        while (flag){
            flag = 0;
            forr (i, 1, q){
                if (low[i] != high[i]){
                    flag = 1;
                    int mid = (low[i] + high[i] + 1) >> 1;
                    qq[mid].pb(i);
                }
            }

            forr (i, 0, m){
                int u = dir[p[id[i]]];
              //  cout << u << " " << tin[u] << " " << tout[u] << endl; 
                if (i){
                    bit2.add(tin[u], tout[u], c[id[i]]);
                }
                for (int j : qq[i]){
                    ll tmp = bit2.get(tin[s[j]]) + bit2.get(tin[t[j]]) - bit2.get(tin[g[j]]) - bit2.get(tin[up[0][g[j]]]);
                    if (tmp <= y[j]){
                        low[j] = i;
                    } else {
                        high[j] = i - 1;
                    }
                }
                qq[i].clear();
            }

            forr (i, 1, n){
                bit2.bit[i] = 0;
            }
        }

        forr (i, 1, q){
            qq[low[i]].pb(i);
        }

        forr (i, 0, m){
            int u = dir[p[id[i]]];
            if (i){
                bit2.add(tin[u], tout[u], 1);
            }
            for (int j : qq[i]){
                ll tmp = bit2.get(tin[s[j]]) + bit2.get(tin[t[j]]) - bit2.get(tin[g[j]]) - bit2.get(tin[up[0][g[j]]]);
                ans[j] = tmp;
            }
            qq[i].clear();
        }

        forr (i, 1 , q){
            x[i] -= numgd[i] - ans[i];
            cout << (x[i] >= 0 ? x[i] : -1) << "\n";
        }
    }
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    #ifdef kaguya
        freopen(file".inp", "r", stdin); freopen(file".out", "w", stdout);
    #endif

    cin >> n >> m >> q;

    forf (i, 1, n){
        cin >> u >> v;
        a[u].pb(i);
        a[v].pb(i);
        ed[i] = u ^ v;
    }

    forr (i, 1, m){
        cin >> p[i] >> c[i];
    }

    forr (i, 1, m){
        tax[p[i]].pb(c[i]);
    }

    forr (i, 1, q){
        cin >> s[i] >> t[i] >> x[i] >> y[i];
    }   

    

    // if (n <= 2000 && m <= 2000 && q <= 2000){
    //     sub1::solve();
    // } else 
    {
        uwu::solve();
    }

    

    return 0;
}
/*



*/

Compilation message (stderr)

currencies.cpp: In function 'void sub1::solve()':
currencies.cpp:74:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |             if (x[i] >= tmp.size()){
      |                 ~~~~~^~~~~~~~~~~~~
currencies.cpp:82:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |                 if (x[i] >= tmp.size() - zz){
      |                     ~~~~~^~~~~~~~~~~~~~~~~~

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