oj.uz

Submission #921220

# Submission time Handle Problem Language Result Execution time Memory
921220 2024-02-03T14:44:56 Z 3as8 Two Currencies (JOI23_currencies) C++14
28 / 100
 168 ms 32728 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 3 ms 860 KB Output is correct
3 Correct 3 ms 860 KB Output is correct
4 Correct 2 ms 860 KB Output is correct
5 Correct 131 ms 23524 KB Output is correct
6 Correct 117 ms 17912 KB Output is correct
7 Correct 115 ms 20416 KB Output is correct
8 Correct 133 ms 20672 KB Output is correct
9 Correct 99 ms 20420 KB Output is correct
10 Correct 136 ms 24264 KB Output is correct
11 Correct 139 ms 24264 KB Output is correct
12 Correct 142 ms 24192 KB Output is correct
13 Correct 143 ms 24208 KB Output is correct
14 Correct 146 ms 24264 KB Output is correct
15 Correct 161 ms 32452 KB Output is correct
16 Correct 168 ms 32728 KB Output is correct
17 Correct 161 ms 31832 KB Output is correct
18 Correct 161 ms 24900 KB Output is correct
19 Correct 166 ms 24772 KB Output is correct
20 Correct 148 ms 25024 KB Output is correct
21 Correct 117 ms 23108 KB Output is correct
22 Correct 135 ms 23184 KB Output is correct
23 Correct 138 ms 23212 KB Output is correct
24 Correct 120 ms 23360 KB Output is correct
25 Correct 130 ms 24772 KB Output is correct
26 Correct 134 ms 24776 KB Output is correct
27 Correct 139 ms 24652 KB Output is correct
28 Correct 114 ms 24172 KB Output is correct
29 Correct 107 ms 24008 KB Output is correct
30 Correct 123 ms 24304 KB Output is correct
31 Correct 136 ms 24268 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -