Submission #921220

#	Time	Username	Problem	Language	Result	Execution time	Memory
921220		3as8	Two Currencies (JOI23_currencies)	C++14	28 / 100	168 ms	32728 KiB

currencies

#include <bits/stdc++.h>

#define ll long long
#define endl "\n"
#define fastIO cin.tie(nullptr); cout.tie(nullptr); ios::sync_with_stdio(false);

#define mid ((l + r) / 2)
#define lChild ((index * 2) + 1)
#define rChild ((index * 2) + 2)

/* ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀    ⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣴⠶⠀⠀⠀⠀⠀⣈⣿⣦⠀⠀⠀⠀
⠀    ⠀⠀⠀⠀⠀⠀⠀⠀⣴⣿⡿⠋⠀⠀⠀⠀⠀⠹⣿⣿⡆⠀⠀⠀
⠀  ⠀  ⠀⠀⠀⠀⠀⠀⢰⣿⣿⣤⣤⣴⣤⣤⣄⠀⢠⣿⣿⠇⠀⠀⠀
⠀ ⠀   ⠀⠀⠀⠀⠀⠀⢸⡿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡟⠀⠀⠀⠀
⠀⠀ ⠀   ⠀⠀⠀⠀⠀⣾⠋⠈⢻⣿⡝⠁⠀⢻⣿⣿⠋⠀⠀⠀⠀⠀
⠀⠀ ⠀   ⠀⠀⠀⠀⠈⣿⣄⣠⣿⣿⣧⣀⣠⣿⣿⣿⠀⠀⠀⠀⠀⠀
⠀⠀  ⠀  ⠀⠀⠀⠀⠀⢻⣿⣿⣿⣿⣿⣿⣿⣿⣿⡟⠀⠀⠀⠀⠀⠀
⠀   ⠀  ⠀⠀⠀⠀⠀⠀⠻⣿⣿⣿⣿⣿⣿⡿⠟⠀⣀⠀⠀⠀⠀⠀
⠀     ⠀⠀⠀⠀⠀⠀⠀⣰⣿⣿⣿⣿⣿⣿⣷⡾⠿⠛⠀⠀⠀⠀⠀
⠀    ⠀⠀⠀⠀⢀⣠⣴⣿⣿⣿⣿⣿⣿⣿⣿⡿⠓⠀⠀⠀⠀⠀⠀⠀
    ⠀⠀⢀⣴⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣦⣀⡀⠀⠀⠀⠀⠀
    ⠀⣰⡟⠉⣼⣿⠟⣡⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣶⣤⡀⠀
    ⢠⣿⠀⠀⣿⣿⣾⠿⠛⣿⣿⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡛⠻⠑⡀
    ⠈⣿⠀⡼⢿⡏⠀⠀⠀⠹⣿⡆⠉⠻⣿⣿⣿⣿⣿⡻⢿⣿⠷⠞⠁
    ⠀⢸⠇⠀⠈⡇⠀⠀⠀⠀⠘⢿⡄⠀⠸⡏⠀⠀⠉⡇⠀⠹⢦⡄⠀
⠀    ⠀⠀⠀⠈⠁⠀⠀⠀⠀⠀⠸⠁⠀⠀⠉⠀⠀⠀⠀⠀⠀⠀⠀⠀

    No cost too great.
            No mind to think.
                    No will to break.
*/

using namespace std;

ll t = 0;
vector<ll> euler;

struct node {
    ll u, i;
};

void dfs(vector<vector<node> >& graph, vector<ll>& last, vector<ll>& depth, ll startIndex, ll p, ll d = 0) {


    euler.push_back(startIndex);
    depth[startIndex] = d;
    last[startIndex] = euler.size() - 1;

    for(auto [el, i] : graph[startIndex]) {
        if(el == p) continue;

        dfs(graph, last, depth, el, startIndex, d + 1);
        euler.push_back(startIndex);
        last[startIndex] = euler.size() - 1;

    }
}

ll merge(ll lC, ll rC, vector<ll>& depth) {

    if(lC == -1) return rC;
    else if(rC == -1) return lC;

    if(depth[lC] < depth[rC]) return lC;
    else return rC;
}

ll build(vector<ll>& tree, vector<ll>& depth, ll l, ll r, ll index) {

    if(l == r) return tree[index] = euler[l];

    return tree[index] = merge( build(tree, depth, l, mid, lChild),  build(tree, depth, mid + 1, r, rChild), depth);
}

ll query(vector<ll>& tree, vector<ll>& depth, ll l, ll r, ll qL, ll qR, ll index) {

    if(r < qL || l > qR) return -1;

    if(qL <= l && r <= qR) return tree[index];

    return merge(query(tree, depth, l, mid, qL, qR, lChild), query(tree, depth, mid + 1, r, qL, qR, rChild), depth);
}

void pre(vector<vector<node> >& graph, vector<ll>& has, vector<ll>& edgeNum, ll curr, ll startIndex, ll p) {

    edgeNum[startIndex] = curr;

    for(auto [el, i] : graph[startIndex]) {
        if(el == p) continue;

        pre(graph, has, edgeNum, curr + has[i], el, startIndex);
    }

}

void solve(ll _) {
    ll n, m, q; cin>>n>>m>>q;


    vector<vector<node> > graph(n);

    for(int i = 0; i < n - 1; i++) {
        ll x, y; cin>>x>>y;
        x--; y--;

        graph[x].push_back({y, i});
        graph[y].push_back({x, i});
    }

    vector<ll> has(n, 0);
    ll globalC;
    for(int i = 0; i < m; i++) {
        ll p, x; cin>>p>>x;
        p--;

        globalC = x;
        has[p] += 1;
    }

    vector<ll> last(n, 0);
    vector<ll> depth(n, 0);
    dfs(graph, last, depth, 0, -1, 0);


    vector<ll> tree(8 * n);
    build(tree, depth, 0, euler.size() - 1, 0);

    vector<ll> edgeNum(n, 0);
    pre(graph, has, edgeNum, 0, 0, -1);

   /* for(auto el : edgeNum) cout<<el<<" ";
    cout<<endl;*/

    for(int i = 0; i < q; i++) {
        ll a, b, g, s; cin>>a>>b>>g>>s;
        a--; b--;

        if(last[a] > last[b]) swap(a, b);

        ll lca = query(tree, depth, 0, euler.size() - 1, last[a], last[b], 0);

        ll num = (edgeNum[a] + edgeNum[b] - (2 * edgeNum[lca]));
        ll canRemove = (s / globalC) + g;

      //  cout<<a + 1<<", "<<b + 1<<" -> "<<num<<endl;

        if(canRemove < num) cout<<-1<<endl;
        else cout<<g - max(0ll, (num - (s / globalC)))<<endl;
    }

}

int main() {
    fastIO

    //freopen("file.in", "r", stdin);
    //freopen("file.out", "w", stdout);

    ll t = 0; solve(t);
}

Compilation message (stderr)

currencies.cpp: In function 'void dfs(std::vector<std::vector<node> >&, std::vector<long long int>&, std::vector<long long int>&, long long int, long long int, long long int)':
currencies.cpp:50:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   50 |     for(auto [el, i] : graph[startIndex]) {
      |              ^
currencies.cpp: In function 'void pre(std::vector<std::vector<node> >&, std::vector<long long int>&, std::vector<long long int>&, long long int, long long int, long long int)':
currencies.cpp:89:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   89 |     for(auto [el, i] : graph[startIndex]) {
      |              ^
currencies.cpp: In function 'void solve(long long int)':
currencies.cpp:144:27: warning: 'globalC' may be used uninitialized in this function [-Wmaybe-uninitialized]
  144 |         ll canRemove = (s / globalC) + g;
      |                        ~~~^~~~~~~~~~

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