Submission #1126496

#TimeUsernameProblemLanguageResultExecution timeMemory
1126496PekibanTwo Currencies (JOI23_currencies)C++17
Compilation error
0 ms0 KiB
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define pb push_back

const int N = 1e5+5 , LOG = 18;
struct EUDQ {
    vector<int> g[N];
    int D[N], up[LOG][N], tin[N], tout[N], n, tm = 0;   
    ll lz[4*N];
    void dfs(int s, int e = -1) {
        tin[s] = ++tm;
        for (auto u : g[s]) {
            if (u == e) continue;
            D[u] = D[s] + 1, up[0][u] = s;
            dfs(u, s);
        }
        tout[s] = tm;
    }
    int jump(int u, int k) {
        for (int i = LOG-1; i >= 0; --i) {
            if ((k >> i) & 1)   u = up[i][u];
        }
        return u;
    }
    void init() {
        dfs(1);
        for (int i = 1; i < LOG; ++i) {
            for (int j = 1; j < N; ++j) {
                up[i][j] = up[i-1][up[i-1][j]];
            }
        }
    }
    void reset() {
        fill(lz, lz+4*(n+1), 0);
    }
    int lca(int u, int v) {
        if (D[u] < D[v])    swap(u, v);
        u = jump(u, D[u] - D[v]);
        if (u == v) return u;
        for (int i = LOG-1; i >= 0; --i) {
            if (up[i][u] != up[i][v])   u = up[i][u], v = up[i][v];
        }
        return up[0][u];
    }
    void push(int i) {
        if (lz[i]) {
            lz[2*i] += lz[i];
            lz[2*i+1] += lz[i];
            lz[i] = 0;
        }
    }
    void upd(int l, int r, int x, int i, int l2, int r2) {
        if (l <= l2 && r2 <= r) {
            lz[i] += x;
            return;
        }
        push(i);
        int m2 = (l2 + r2)/2;
        if (l <= m2)    upd(l, r, x, 2*i, l2, m2);
        if (m2+1 <= r)  upd(l, r, x, 2*i+1, m2+1, r2);
    }
    void add(int u, int v, int x) {
        if (D[u] < D[v])    swap(u, v);
        upd(tin[u], tout[u], x, 1, 1, n);
    }
    ll qry(int p, int i, int l2, int r2) {
        if (l2 == r2)   return lz[i];
        push(i);
        int m2 = (l2 + r2)/2;
        if (p <= m2)    return qry(p, 2*i, l2, m2);
        return qry(p, 2*i+1, m2+1, r2);
    }
    ll qry(int p) {
        return qry(p, 1, 1, n);
    }
    ll calc(int u, int v) {
        return qry(tin[u]) + qry(tin[v]) - 2*qry(tin[lca(u, v)]);
    }
} T;
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, m, q;
    cin >> n >> m >> q; T.n = n;
    array<int, 2> E[n];
    for (int i = 1; i < n; ++i) {
        int u, v;
        cin >> u >> v;
        T.g[u].pb(v); T.g[v].pb(u);
        E[i] = {u, v};
    }
    pair<int, int> e[m+1];
    for (int i = 1; i <= m; ++i) {
        cin >> e[i].first >> e[i].second;
    }
    sort(e+1, e+m+1);
    for (int i = 1; i <= m; ++i)    swap(e[i][0], e[i][1]);
    array<ll, 4> qu[q+1];
    for (int i = 1; i <= q; ++i) {
        cin >> qu[i][0] >> qu[i][1] >> qu[i][2] >> qu[i][3];
    }
    for (int i = 1; i <= q; ++i) {
        cout << qu[i][0] << ' ' << qu[i][1] << ' ' << qu[i][2] << ' ' << qu[i][3] << '\n';
    }
    for (int i = 1; i <= m; ++i) {
        T.add(E[e[i][0]][0], E[e[i][0]][1], e[i][1]);
        for (int j = 1; j <= q; ++j) {
            if (T.calc(qu[j][0], qu[j][1]) <= qu[j][3]) P[j] = i;
        }
    }
    T.reset();
    vector<int> B[m+1];
    for (int i = 1; i <= q; ++i)    B[P[i]].pb(i);
    for (int i = 0; i <= m; ++i) {
        if (i)  T.add(E[e[i][0]][0], E[e[i][0]][1], 1);
        for (auto j : B[i]) {
            qu[j][2] += T.calc(qu[j][0], qu[j][1]);
        }
    }
    for (int i = 1; i <= q; ++i) {
        cout << max(-1LL, qu[i][2] - T.calc(qu[i][0], qu[i][1])) << '\n';
    }
}

Compilation message (stderr)

currencies.cpp: In function 'int main()':
currencies.cpp:99:46: error: no match for 'operator[]' (operand types are 'std::pair<int, int>' and 'int')
   99 |     for (int i = 1; i <= m; ++i)    swap(e[i][0], e[i][1]);
      |                                              ^
currencies.cpp:99:55: error: no match for 'operator[]' (operand types are 'std::pair<int, int>' and 'int')
   99 |     for (int i = 1; i <= m; ++i)    swap(e[i][0], e[i][1]);
      |                                                       ^
currencies.cpp:108:21: error: no match for 'operator[]' (operand types are 'std::pair<int, int>' and 'int')
  108 |         T.add(E[e[i][0]][0], E[e[i][0]][1], e[i][1]);
      |                     ^
currencies.cpp:108:36: error: no match for 'operator[]' (operand types are 'std::pair<int, int>' and 'int')
  108 |         T.add(E[e[i][0]][0], E[e[i][0]][1], e[i][1]);
      |                                    ^
currencies.cpp:108:49: error: no match for 'operator[]' (operand types are 'std::pair<int, int>' and 'int')
  108 |         T.add(E[e[i][0]][0], E[e[i][0]][1], e[i][1]);
      |                                                 ^
currencies.cpp:110:57: error: 'P' was not declared in this scope
  110 |             if (T.calc(qu[j][0], qu[j][1]) <= qu[j][3]) P[j] = i;
      |                                                         ^
currencies.cpp:115:39: error: 'P' was not declared in this scope
  115 |     for (int i = 1; i <= q; ++i)    B[P[i]].pb(i);
      |                                       ^
currencies.cpp:117:29: error: no match for 'operator[]' (operand types are 'std::pair<int, int>' and 'int')
  117 |         if (i)  T.add(E[e[i][0]][0], E[e[i][0]][1], 1);
      |                             ^
currencies.cpp:117:44: error: no match for 'operator[]' (operand types are 'std::pair<int, int>' and 'int')
  117 |         if (i)  T.add(E[e[i][0]][0], E[e[i][0]][1], 1);
      |                                            ^