oj.uz

Submission #805210

# Submission time Handle Problem Language Result Execution time Memory
805210 2023-08-03T14:06:44 Z Sharky Two Currencies (JOI23_currencies) C++17
28 / 100
 314 ms 63496 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define sz(x) (int)x.size()
const int maxn = 1E5+8;
const int lgn = 18;

vector<pair<int, vector<int>>> adj[maxn];

struct edge {
    int u, v;
    vector<int> c;
};

vector<edge> edges;
map<pair<int, int>, int> mp;
int n, m, q, C, ls[maxn], dep[maxn], di[maxn], lift[maxn][lgn];

void dfs(int u, int pr = -1) {
    for (auto& [v, c] : adj[u]) {
        if (v == pr) continue;
        dfs(v, u);
        ls[v] = u;
    }
}

void dfs_pre(int u, int pr = -1) {
    for (int i = 1; i < lgn; i++) lift[u][i] = lift[lift[u][i-1]][i-1];
    for (auto& [v, c] : adj[u]) {
        if (v == pr) continue;
        dep[v] = dep[u] + 1;
        di[v] = di[u] + sz(c);
        lift[v][0] = u;
        dfs_pre(v, u);
    }
}

int jump(int s, int dist) {
    for (int i = lgn - 1; i >= 0; i--) {
        if (dist & (1 << i)) s = lift[s][i];
    }
    return s;
}

int getlca(int u, int v) {
    if (dep[u] < dep[v]) swap(u, v);
    u = jump(u, dep[u] - dep[v]);
    if (u == v) return u;
    for (int i = lgn - 1; i >= 0; i--) {
        int ut = lift[u][i], vt = lift[v][i];
        if (ut != vt) u = ut, v = vt;
    }
    return lift[u][0];
}

int32_t main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m >> q;
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        edges.push_back((edge) {u, v, {}});
        mp[{u, v}] = mp[{v, u}] = i;
    }
    for (int i = 1; i <= m; i++) {
        int p, c;
        cin >> p >> c;
        C = c;
        edges[p-1].c.push_back(c);
    }
    for (auto& [u, v, c] : edges) {
        adj[u].push_back({v, c});
        adj[v].push_back({u, c});
    }
    lift[1][0] = 1; 
    dfs_pre(1);
    while (q--) {
        int s, t, x, y;
        cin >> s >> t >> x >> y;
        int lca = getlca(s, t);
        int cnt = di[s] + di[t] - 2 * di[lca];
        cnt -= (y / C);
        if (cnt < 0) cnt = 0;
        if (x - cnt < 0) cout << "-1\n";
        else cout << x - cnt << "\n";
    }
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2644 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 1 ms 2644 KB Output is correct
2 Correct 4 ms 3540 KB Output is correct
3 Correct 6 ms 3540 KB Output is correct
4 Correct 4 ms 3636 KB Output is correct
5 Correct 224 ms 50968 KB Output is correct
6 Correct 180 ms 39608 KB Output is correct
7 Correct 208 ms 45312 KB Output is correct
8 Correct 190 ms 46268 KB Output is correct
9 Correct 186 ms 46232 KB Output is correct
10 Correct 254 ms 54964 KB Output is correct
11 Correct 239 ms 55000 KB Output is correct
12 Correct 253 ms 55032 KB Output is correct
13 Correct 230 ms 54992 KB Output is correct
14 Correct 244 ms 54968 KB Output is correct
15 Correct 300 ms 63092 KB Output is correct
16 Correct 282 ms 63496 KB Output is correct
17 Correct 311 ms 62588 KB Output is correct
18 Correct 292 ms 55608 KB Output is correct
19 Correct 284 ms 55524 KB Output is correct
20 Correct 314 ms 55716 KB Output is correct
21 Correct 253 ms 53500 KB Output is correct
22 Correct 190 ms 53608 KB Output is correct
23 Correct 213 ms 53676 KB Output is correct
24 Correct 194 ms 53640 KB Output is correct
25 Correct 238 ms 54144 KB Output is correct
26 Correct 239 ms 54140 KB Output is correct
27 Correct 233 ms 54088 KB Output is correct
28 Correct 282 ms 54812 KB Output is correct
29 Correct 248 ms 54900 KB Output is correct
30 Correct 257 ms 55008 KB Output is correct
31 Correct 214 ms 55020 KB Output is correct

Subtask #3
0 / 30.0

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