oj.uz

Submission #888624

# Submission time Handle Problem Language Result Execution time Memory
888624 2023-12-18T04:25:25 Z kylych03 Two Currencies (JOI23_currencies) C++14
28 / 100
 257 ms 47876 KB 
#include <bits/stdc++.h>

using namespace std;

#define all(x) x.begin(), x.end()
#define ar array
#define pb push_back
#define ln '\n'
#define int long long

using i64 = long long;

template <class F, class _S>
bool chmin(F &u, const _S &v){
    bool flag = false;
    if ( u > v ){
        u = v; flag |= true;
    }
    return flag;
}

template <class F, class _S>
bool chmax(F &u, const _S &v){
    bool flag = false;
    if ( u < v ){
        u = v; flag |= true;
    }
    return flag;
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, q; cin >> n >> m >> q;
    vector <vector<ar<int,2>>> G(n);
    for ( int i = 0; i + 1 < n; i++ ){
        int u, v; cin >> u >> v;
        --u, --v;
        G[u].pb({v, i});
        G[v].pb({u, i});
    }
    vector <int> pt(n);
    int cost = -1;
    for ( int i = 0; i < m; i++ ){
        int p, c; cin >> p >> c;
        pt[--p]++;
        cost = c;
    }
    vector <vector<int>> up(20, vector <int> (n)), sum(20, vector <int> (n));
    vector <int> d(n), dp(n);
    auto dfs = [&](auto dfs, int u, int p) -> void{
        up[0][u] = p;
        for ( int i = 1; i < 20; i++ ){
            up[i][u] = up[i - 1][up[i - 1][u]];
        }
        for ( auto &[v, i]: G[u] ){
            if ( v != p ){
                d[v] = d[u] + 1;
                dp[v] = dp[u] + pt[i];
                dfs(dfs, v, u);
            }
        }
    };
    dfs(dfs, 0, 0);
    auto lca = [&](int u, int v){
        if ( d[u] < d[v] ) swap(u, v);
        int df = d[u] - d[v];
        for ( int i = 0; i < 20; i++ ){
            if ( df >> i & 1 ){
                u = up[i][u];
            }
        }
        if ( u == v ){
            return u;
        }
        for ( int i = 19; i >= 0; i-- ){
            if ( up[i][u] != up[i][v] ){
                u = up[i][u];
                v = up[i][v];
            }
        }
        return up[0][u];
    };
    auto get = [&](int u, int v){
        return dp[u] + dp[v] - dp[lca(u, v)] * 2;
    };
    while ( q-- ){
        int s, t, x, y;
        cin >> s >> t >> x >> y;
        --s, --t;
        cout << max(-1LL, x - max(0LL, get(s, t) - y / cost)) << ln;
    }

    cout << '\n';
}

Compilation message

currencies.cpp: In lambda function:
currencies.cpp:57:21: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   57 |         for ( auto &[v, i]: G[u] ){
      |                     ^

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 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 2 ms 1288 KB Output is correct
3 Correct 2 ms 1368 KB Output is correct
4 Correct 2 ms 1116 KB Output is correct
5 Correct 141 ms 41724 KB Output is correct
6 Correct 119 ms 27820 KB Output is correct
7 Correct 135 ms 34516 KB Output is correct
8 Correct 121 ms 36268 KB Output is correct
9 Correct 119 ms 35856 KB Output is correct
10 Correct 171 ms 41792 KB Output is correct
11 Correct 162 ms 41792 KB Output is correct
12 Correct 165 ms 41740 KB Output is correct
13 Correct 173 ms 41916 KB Output is correct
14 Correct 163 ms 41792 KB Output is correct
15 Correct 190 ms 47424 KB Output is correct
16 Correct 186 ms 47876 KB Output is correct
17 Correct 232 ms 47168 KB Output is correct
18 Correct 257 ms 42044 KB Output is correct
19 Correct 219 ms 42048 KB Output is correct
20 Correct 227 ms 42116 KB Output is correct
21 Correct 146 ms 41308 KB Output is correct
22 Correct 146 ms 41152 KB Output is correct
23 Correct 145 ms 41200 KB Output is correct
24 Correct 140 ms 41312 KB Output is correct
25 Correct 172 ms 42148 KB Output is correct
26 Correct 176 ms 41912 KB Output is correct
27 Correct 151 ms 41892 KB Output is correct
28 Correct 121 ms 41736 KB Output is correct
29 Correct 120 ms 41792 KB Output is correct
30 Correct 129 ms 41744 KB Output is correct
31 Correct 125 ms 41796 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 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 344 KB Output isn't correct
2 Halted 0 ms 0 KB -