oj.uz

Submission #888623

# Submission time Handle Problem Language Result Execution time Memory
888623 2023-12-18T04:22:27 Z vjudge1 Two Currencies (JOI23_currencies) C++17
28 / 100
 214 ms 53608 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';
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 600 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 344 KB Output is correct
2 Correct 2 ms 1172 KB Output is correct
3 Correct 2 ms 1172 KB Output is correct
4 Correct 2 ms 1196 KB Output is correct
5 Correct 142 ms 45972 KB Output is correct
6 Correct 131 ms 32804 KB Output is correct
7 Correct 152 ms 38972 KB Output is correct
8 Correct 127 ms 40108 KB Output is correct
9 Correct 119 ms 39704 KB Output is correct
10 Correct 174 ms 46952 KB Output is correct
11 Correct 171 ms 46912 KB Output is correct
12 Correct 173 ms 47000 KB Output is correct
13 Correct 175 ms 46848 KB Output is correct
14 Correct 172 ms 46912 KB Output is correct
15 Correct 198 ms 53316 KB Output is correct
16 Correct 187 ms 53608 KB Output is correct
17 Correct 206 ms 52968 KB Output is correct
18 Correct 214 ms 47648 KB Output is correct
19 Correct 204 ms 47600 KB Output is correct
20 Correct 204 ms 47660 KB Output is correct
21 Correct 149 ms 45764 KB Output is correct
22 Correct 143 ms 45880 KB Output is correct
23 Correct 141 ms 45916 KB Output is correct
24 Correct 157 ms 46320 KB Output is correct
25 Correct 152 ms 47428 KB Output is correct
26 Correct 152 ms 47408 KB Output is correct
27 Correct 137 ms 47392 KB Output is correct
28 Correct 120 ms 46912 KB Output is correct
29 Correct 119 ms 46944 KB Output is correct
30 Correct 124 ms 46988 KB Output is correct
31 Correct 135 ms 47168 KB Output is correct

Subtask #3
0 / 30.0

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

Subtask #4
0 / 32.0

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