oj.uz

Submission #888662

# Submission time Handle Problem Language Result Execution time Memory
888662 2023-12-18T05:14:50 Z vjudge1 Two Currencies (JOI23_currencies) C++17
38 / 100
 432 ms 51396 KB 
#include <bits/stdc++.h>
using namespace std;
typedef int64_t ll;
#define all(x) x.begin(), x.end()
//#define size(x) (int)x.size()

template<class S, class T> 
bool chmin(S &a, const T &b) {
    return (a > b ? (a = b) == b : false);
}
template<class S, class T> 
bool chmax(S &a, const T &b) {
    return (a < b ? (a = b) == b : false);
}
const int inf = 1e9;
const ll INF = 1e18;
const int mod = 998244353;
const int N = 1e5 + 1;

int C;

signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n, m, q;
    cin >> n >> m >> q;
    int a[n], b[n];
    vector<int> c[n], g[n + 1];
    map<pair<int, int>, int> ind;
    for (int i = 1; i < n; ++i) {
        cin >> a[i] >> b[i];
        g[a[i]].push_back(b[i]);
        g[b[i]].push_back(a[i]);
        ind[{a[i], b[i]}] = i;
        ind[{b[i], a[i]}] = i;
    }
    for (int i = 0; i < m; ++i) {
        int j, w;
        cin >> j >> w;
        C = w;
        c[j].push_back(w);
    }
    if (n <= 2000 && m <= 2000 && q <= 2000) {
        vector<int> p(n + 1, 0);
        function<void(int, int)> dfs = [&](int v, int parent) {
            for (int to : g[v]) {
                if (to != parent) {
                    p[to] = v;
                    dfs(to, v);
                }
            }
        };
        while (q--) {
            int a, b, x; ll y;
            cin >> a >> b >> x >> y;
            vector<int> path;
            dfs(a, 0);
            int v = b;
            while (v) {
                path.push_back(v);
                v = p[v];
            }
            vector<int> cost;
            for (int i = 0; i + 1 < (int)path.size(); ++i) {
                for (int j : c[ind[{path[i], path[i + 1]}]]) {
                    cost.push_back(j);
                }
            }
            sort(all(cost), greater<int>());
            while (!cost.empty() && y - cost.back() >= 0) {
                y -= cost.back();
                cost.pop_back();
            }
            x -= size(cost);
            cout << (x < 0 ? -1 : x) << '\n';
            for (int i = 1; i <= n; ++i) {
                p[i] = 0;
            }
        }
    } else {
        vector<int> tin(n + 1), tout(n + 1), val(n + 1, 0);
        vector<vector<int>> up(n + 1, vector<int> (17, 1));
        int timer = -1;
        function<void(int, int)> dfs = [&](int v, int p) {
            val[v] += (int)c[ind[{v, p}]].size();
            tin[v] = ++timer;
            up[v][0] = p;
            for (int i = 1; i < 17; ++i) {
                up[v][i] = up[up[v][i - 1]][i - 1];
            }
            for (int to : g[v]) {
                if (to != p) {
                    val[to] += val[v];
                    dfs(to, v);
                }
            }
            tout[v] = ++timer;
        };
        auto upper = [&](int u, int v) {
            return tin[u] <= tin[v] && tout[u] >= tout[v];
        };
        auto get_lca = [&](int u, int v) {
            if (upper(u, v)) return u;
            if (upper(v, u)) return v;
            for (int i = 16; i >= 0; --i) {
                if (!upper(up[u][i], v)) {
                    u = up[u][i];
                }
            }
            return up[u][0];
        };
        dfs(1, 1);
        while (q--) {
            int a, b, x; ll y;
            cin >> a >> b >> x >> y;
            if (upper(a, b)) {
                int need = val[b] - val[a];
                y /= C;
                if (need <= y) {
                    cout << x << '\n';
                } else {
                    need -= y;
                    x -= need;
                    cout << (x < 0 ? -1 : x) << '\n';
                }
            } else if (upper(b, a)) {
                swap(a, b);
                int need = val[b] - val[a];
                y /= C;
                if (need <= y) {
                    cout << x << '\n';
                } else {
                    need -= y;
                    x -= need;
                    cout << (x < 0 ? -1 : x) << '\n';
                }
            } else {
                int lca = get_lca(a, b);
                int need = val[b] + val[a] - val[lca] * 2;
                y /= C;
                if (need <= y) {
                    cout << x << '\n';
                } else {
                    need -= y;
                    x -= need;
                    cout << (x < 0 ? -1 : x) << '\n';
                }
            }
        }
    }
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 456 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 24 ms 960 KB Output is correct
6 Correct 40 ms 860 KB Output is correct
7 Correct 25 ms 604 KB Output is correct
8 Correct 43 ms 860 KB Output is correct
9 Correct 44 ms 1016 KB Output is correct
10 Correct 43 ms 856 KB Output is correct
11 Correct 47 ms 856 KB Output is correct
12 Correct 45 ms 860 KB Output is correct
13 Correct 275 ms 1176 KB Output is correct
14 Correct 281 ms 1364 KB Output is correct
15 Correct 154 ms 1096 KB Output is correct
16 Correct 133 ms 856 KB Output is correct
17 Correct 115 ms 1040 KB Output is correct
18 Correct 160 ms 1084 KB Output is correct
19 Correct 27 ms 856 KB Output is correct
20 Correct 27 ms 1016 KB Output is correct
21 Correct 28 ms 860 KB Output is correct
22 Correct 28 ms 1012 KB Output is correct
23 Correct 96 ms 1000 KB Output is correct
24 Correct 96 ms 860 KB Output is correct
25 Correct 99 ms 1000 KB Output is correct
26 Correct 41 ms 860 KB Output is correct
27 Correct 41 ms 1264 KB Output is correct
28 Correct 41 ms 860 KB Output is correct
29 Correct 39 ms 980 KB Output is correct
30 Correct 83 ms 860 KB Output is correct
31 Correct 43 ms 860 KB Output is correct
32 Correct 44 ms 860 KB Output is correct
33 Correct 175 ms 1176 KB Output is correct
34 Correct 176 ms 1188 KB Output is correct
35 Correct 176 ms 1116 KB Output is correct

Subtask #2
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 44 ms 996 KB Output is correct
3 Correct 44 ms 992 KB Output is correct
4 Correct 46 ms 996 KB Output is correct
5 Correct 325 ms 39200 KB Output is correct
6 Correct 233 ms 28504 KB Output is correct
7 Correct 260 ms 33344 KB Output is correct
8 Correct 276 ms 33864 KB Output is correct
9 Correct 305 ms 33892 KB Output is correct
10 Correct 364 ms 40280 KB Output is correct
11 Correct 358 ms 40444 KB Output is correct
12 Correct 350 ms 40312 KB Output is correct
13 Correct 339 ms 40272 KB Output is correct
14 Correct 332 ms 40368 KB Output is correct
15 Correct 398 ms 50796 KB Output is correct
16 Correct 410 ms 51396 KB Output is correct
17 Correct 422 ms 50212 KB Output is correct
18 Correct 414 ms 40808 KB Output is correct
19 Correct 432 ms 40812 KB Output is correct
20 Correct 420 ms 40756 KB Output is correct
21 Correct 303 ms 39820 KB Output is correct
22 Correct 285 ms 40136 KB Output is correct
23 Correct 280 ms 40140 KB Output is correct
24 Correct 281 ms 40016 KB Output is correct
25 Correct 353 ms 39984 KB Output is correct
26 Correct 343 ms 40228 KB Output is correct
27 Correct 393 ms 40048 KB Output is correct
28 Correct 370 ms 40152 KB Output is correct
29 Correct 346 ms 39920 KB Output is correct
30 Correct 325 ms 40392 KB Output is correct
31 Correct 301 ms 40264 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 184 ms 1172 KB Output is correct
3 Correct 180 ms 1116 KB Output is correct
4 Correct 186 ms 1176 KB Output is correct
5 Incorrect 134 ms 46988 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 456 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 24 ms 960 KB Output is correct
6 Correct 40 ms 860 KB Output is correct
7 Correct 25 ms 604 KB Output is correct
8 Correct 43 ms 860 KB Output is correct
9 Correct 44 ms 1016 KB Output is correct
10 Correct 43 ms 856 KB Output is correct
11 Correct 47 ms 856 KB Output is correct
12 Correct 45 ms 860 KB Output is correct
13 Correct 275 ms 1176 KB Output is correct
14 Correct 281 ms 1364 KB Output is correct
15 Correct 154 ms 1096 KB Output is correct
16 Correct 133 ms 856 KB Output is correct
17 Correct 115 ms 1040 KB Output is correct
18 Correct 160 ms 1084 KB Output is correct
19 Correct 27 ms 856 KB Output is correct
20 Correct 27 ms 1016 KB Output is correct
21 Correct 28 ms 860 KB Output is correct
22 Correct 28 ms 1012 KB Output is correct
23 Correct 96 ms 1000 KB Output is correct
24 Correct 96 ms 860 KB Output is correct
25 Correct 99 ms 1000 KB Output is correct
26 Correct 41 ms 860 KB Output is correct
27 Correct 41 ms 1264 KB Output is correct
28 Correct 41 ms 860 KB Output is correct
29 Correct 39 ms 980 KB Output is correct
30 Correct 83 ms 860 KB Output is correct
31 Correct 43 ms 860 KB Output is correct
32 Correct 44 ms 860 KB Output is correct
33 Correct 175 ms 1176 KB Output is correct
34 Correct 176 ms 1188 KB Output is correct
35 Correct 176 ms 1116 KB Output is correct
36 Correct 0 ms 344 KB Output is correct
37 Correct 44 ms 996 KB Output is correct
38 Correct 44 ms 992 KB Output is correct
39 Correct 46 ms 996 KB Output is correct
40 Correct 325 ms 39200 KB Output is correct
41 Correct 233 ms 28504 KB Output is correct
42 Correct 260 ms 33344 KB Output is correct
43 Correct 276 ms 33864 KB Output is correct
44 Correct 305 ms 33892 KB Output is correct
45 Correct 364 ms 40280 KB Output is correct
46 Correct 358 ms 40444 KB Output is correct
47 Correct 350 ms 40312 KB Output is correct
48 Correct 339 ms 40272 KB Output is correct
49 Correct 332 ms 40368 KB Output is correct
50 Correct 398 ms 50796 KB Output is correct
51 Correct 410 ms 51396 KB Output is correct
52 Correct 422 ms 50212 KB Output is correct
53 Correct 414 ms 40808 KB Output is correct
54 Correct 432 ms 40812 KB Output is correct
55 Correct 420 ms 40756 KB Output is correct
56 Correct 303 ms 39820 KB Output is correct
57 Correct 285 ms 40136 KB Output is correct
58 Correct 280 ms 40140 KB Output is correct
59 Correct 281 ms 40016 KB Output is correct
60 Correct 353 ms 39984 KB Output is correct
61 Correct 343 ms 40228 KB Output is correct
62 Correct 393 ms 40048 KB Output is correct
63 Correct 370 ms 40152 KB Output is correct
64 Correct 346 ms 39920 KB Output is correct
65 Correct 325 ms 40392 KB Output is correct
66 Correct 301 ms 40264 KB Output is correct
67 Correct 0 ms 344 KB Output is correct
68 Correct 184 ms 1172 KB Output is correct
69 Correct 180 ms 1116 KB Output is correct
70 Correct 186 ms 1176 KB Output is correct
71 Incorrect 134 ms 46988 KB Output isn't correct
72 Halted 0 ms 0 KB -