Submission #843547

#	Time	Username	Problem	Language	Result	Execution time	Memory
843547		Quadrilateral	Two Currencies (JOI23_currencies)	C++17	100 / 100	3515 ms	65820 KiB

currencies

#pragma GCC optimize("Ofast")
#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
#define MAXN 100010
using namespace std;

typedef long long ll;

int N, M, Q;
int parent[20][MAXN];
int depth[MAXN];
int in[MAXN], out[MAXN];
int max_height;
int dfs_ordering[MAXN];
vector<int> adj[MAXN];

typedef struct save_points {
    ll s, e, val;
    bool operator < (const save_points& right) {
        return val < right.val;
    }
} save_points;

typedef struct Query {
    ll s, t, x, y;
} Query;

vector<save_points> SP;
vector<Query> queries;
int l[MAXN], r[MAXN];
vector< pair<int, int> > roads;

void fastIO() { ios_base::sync_with_stdio(0); cin.tie(0); }

void input() {
    cin >> N >> M >> Q;
    roads.resize(N);
    for (int i = 1; i <= N - 1; i++) {
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
        roads[i] = { min(a, b), max(a, b) };
    }
    for (int i = 1; i <= M; i++) {
        int a, b;
        cin >> a >> b;
        save_points tmp = { roads[a].first, roads[a].second, b };
        SP.push_back(tmp);
    }
    sort(SP.begin(), SP.end());
    queries.resize(Q);
    for (int i = 0; i < Q; i++)
        cin >> queries[i].s >> queries[i].t >> queries[i].x >> queries[i].y;
}

int Euler_tour_idx, ordering_idx;

void Euler_tour(int n, int dep) { // set in, out, depth, parent
    dfs_ordering[n] = ++ordering_idx;
    in[n] = ++Euler_tour_idx;
    depth[n] = dep;
    for (int i = 0; i < adj[n].size(); i++) {
        int next = adj[n][i];
        if (in[next]) continue;
        parent[0][next] = n;
        Euler_tour(next, dep + 1);
    }
    ++Euler_tour_idx;
    out[n] = Euler_tour_idx;
}

void set_parent() { // for faster lca
    int tmp = N, cnt = 0;
    while (tmp > 1) {
        tmp >>= 1;
        cnt++;
    }
    max_height = cnt;
    for (int k = 1; k <= max_height; k++)
        for (int i = 2; i <= N; i++)
            if (parent[k - 1][i])
                parent[k][i] = parent[k - 1][parent[k - 1][i]];
}

int LCA(int a, int b) { // returns lca of node a and b
    if (depth[a] != depth[b]) {
        if (depth[a] < depth[b]) swap(a, b); // a is deeper
        ll dif = depth[a] - depth[b];
        for (ll i = 0; dif > 0; i++) {
            if (dif & 1) a = parent[i][a];
            dif >>= 1;
        }
    }

    if (a != b) {
        for (int k = max_height; 0 <= k; k--) {
            if (parent[k][a] != 0 && parent[k][a] != parent[k][b]) {
                a = parent[k][a];
                b = parent[k][b];
            }
        }
        a = parent[0][a];
    }

    return a;
}

ll tree1[8 * MAXN], tree2[8 * MAXN], tree3[8 * MAXN];

void update(ll tree[], int n, int s, int e, int tgIdx, ll val) {
    if (s == e) {
        tree[n] += val;
        return;
    }
    int lch = n << 1, rch = lch | 1, m = s + e >> 1;
    if (tgIdx <= m) update(tree, lch, s, m, tgIdx, val);
    else update(tree, rch, m + 1, e, tgIdx, val);
    tree[n] = tree[lch] + tree[rch];
}

ll query(ll tree[], int n, int s, int e, int fs, int fe) {
    if (e < fs || fe < s) return 0;
    if (fs <= s && e <= fe) return tree[n];
    int lch = n << 1, rch = lch | 1, m = s + e >> 1;
    ll left = query(tree, lch, s, m, fs, fe);
    ll right = query(tree, rch, m + 1, e, fs, fe);
    return left + right;
}

void segclear(int s = 1, int e = Euler_tour_idx, int n = 1) {
    tree1[n] = tree3[n] = 0;
    if (s == e) return;
    int m = s + e >> 1;
    segclear(s, m, n << 1);
    segclear(m + 1, e, n << 1 | 1);
}

vector<int> g[MAXN];
int ans[MAXN];
int totSP[MAXN]{};
int cnts[MAXN]{};

void solve() {
    for (int i = 0; i < MAXN; i++)
        ans[i] = -1;
    Euler_tour(1, 0); // for setting in, out, par
    set_parent(); // for faster LCA(O(logN))
    for (int i = 0; i < Q; i++) { // set for PBS
        l[i] = -1;
        r[i] = M;
    }

    for (int i = 0; i < M; i++) {
        int S = SP[i].s, E = SP[i].e, VAL = SP[i].val;
        if (in[E] <= in[S] && in[S] <= out[E]) swap(S, E);
        update(tree2, 1, 1, Euler_tour_idx, in[E], 1); // SP 추가
        update(tree2, 1, 1, Euler_tour_idx, out[E], -1);
    }

    for (int j = 0; j < Q; j++) {
        int tmp_lca = LCA(queries[j].s, queries[j].t);
        ll tmp = query(tree2, 1, 1, Euler_tour_idx, 1, in[queries[j].s]) + query(tree2, 1, 1, Euler_tour_idx, 1, in[queries[j].t]) - 2 * query(tree2, 1, 1, Euler_tour_idx, 1, in[tmp_lca]);
        totSP[j] = tmp;
    }

    while (1) {
        for (int i = 0; i < MAXN; i++)
            g[i].clear();
        segclear();
        bool flag = 0;
        for (int i = 0; i < Q; i++) {
            if (l[i] + 1 == r[i]) continue;
            flag = 1; g[l[i] + r[i] >> 1].push_back(i);
        }
        if (!flag) break;

        for (int i = 0; i < M; i++) {
            ll S = SP[i].s, E = SP[i].e, VAL = SP[i].val;
            if (in[E] <= in[S] && in[S] <= out[E]) swap(S, E);
            update(tree1, 1, 1, Euler_tour_idx, in[E], VAL); // SP (은화 가중치) 추가
            update(tree1, 1, 1, Euler_tour_idx, out[E], -VAL);
            update(tree3, 1, 1, Euler_tour_idx, in[E], 1); // SP (단순 개수) 추가
            update(tree3, 1, 1, Euler_tour_idx, out[E], -1);
            for (auto j : g[i]) {
                int tmp_lca = LCA(queries[j].s, queries[j].t);
                ll tmp = query(tree1, 1, 1, Euler_tour_idx, 1, in[queries[j].s]) + query(tree1, 1, 1, Euler_tour_idx, 1, in[queries[j].t]) - 2 * query(tree1, 1, 1, Euler_tour_idx, 1, in[tmp_lca]);
                ll tmp3 = query(tree3, 1, 1, Euler_tour_idx, 1, in[queries[j].s]) + query(tree3, 1, 1, Euler_tour_idx, 1, in[queries[j].t]) - 2 * query(tree3, 1, 1, Euler_tour_idx, 1, in[tmp_lca]);
                if (tmp <= queries[j].y) {
                    ans[j] = max((ll)ans[j], queries[j].x - totSP[j] + tmp3);
                    l[j] = i;
                }
                else r[j] = i;
            }
        }
    }
}

void output() {
    for (int i = 0; i < Q; i++) {
        if (ans[i] == -1 && queries[i].x >= totSP[i])
            ans[i] = queries[i].x - totSP[i];
        cout << ans[i] << '\n';
    }
}

int main() {
    fastIO();
    input();
    solve();
    output();
    return 0;
}

Compilation message (stderr)

currencies.cpp: In function 'void Euler_tour(int, int)':
currencies.cpp:65:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |     for (int i = 0; i < adj[n].size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~
currencies.cpp: In function 'void update(ll*, int, int, int, int, ll)':
currencies.cpp:118:44: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  118 |     int lch = n << 1, rch = lch | 1, m = s + e >> 1;
      |                                          ~~^~~
currencies.cpp: In function 'll query(ll*, int, int, int, int, int)':
currencies.cpp:127:44: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  127 |     int lch = n << 1, rch = lch | 1, m = s + e >> 1;
      |                                          ~~^~~
currencies.cpp: In function 'void segclear(int, int, int)':
currencies.cpp:136:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  136 |     int m = s + e >> 1;
      |             ~~^~~
currencies.cpp: In function 'void solve()':
currencies.cpp:157:39: warning: unused variable 'VAL' [-Wunused-variable]
  157 |         int S = SP[i].s, E = SP[i].e, VAL = SP[i].val;
      |                                       ^~~
currencies.cpp:176:30: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  176 |             flag = 1; g[l[i] + r[i] >> 1].push_back(i);
      |                         ~~~~~^~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 28 / 28
• Subtask 3: 30 / 30
• Subtask 4: 32 / 32