oj.uz

Submission #805209

# Submission time Handle Problem Language Result Execution time Memory
805209 2023-08-03T14:05:31 Z Sharky Two Currencies (JOI23_currencies) C++17
0 / 100
 4 ms 3540 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);
        dfs_pre(v, u);
        lift[v][0] = 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 2 ms 2644 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Incorrect 4 ms 3540 KB Output isn't correct
3 Halted 0 ms 0 KB -

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 2 ms 2644 KB Output isn't correct
2 Halted 0 ms 0 KB -