제출 #1247374

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1247374		azaylibelz	Two Currencies (JOI23_currencies)	C++20	0 / 100	55 ms	6472 KiB

currencies

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <map>

using namespace std;
typedef long long ll;

const ll INF = 4e18; // A large value representing infinity
const int MAXN = 100005;
const int MAXQ = 100005;

struct Query {
    int id;
    int s, t;
    ll x, y;
};

// Graph and checkpoint data
vector<pair<int, int>> adj[MAXN];
vector<ll> road_checkpoints[MAXN];
vector<Query> all_queries;

int N, M, Q;
ll final_ans[MAXQ];

// --- Centroid Decomposition Structures ---
int subtree_size[MAXN];
bool is_removed[MAXN];

// Structures to hold path info relative to the current centroid
struct PathInfo {
    vector<ll> costs;
    vector<ll> p_sums;
};
map<int, PathInfo> path_info_map; // node -> path info from centroid
int sub_parent[MAXN];

// --- Centroid Decomposition Core Logic ---

void dfs_size(int u, int p) {
    subtree_size[u] = 1;
    for (auto& edge : adj[u]) {
        int v = edge.first;
        if (v != p && !is_removed[v]) {
            dfs_size(v, u);
            subtree_size[u] += subtree_size[v];
        }
    }
}

int find_centroid(int u, int p, int total_size) {
    for (auto& edge : adj[u]) {
        int v = edge.first;
        if (v != p && !is_removed[v] && subtree_size[v] * 2 > total_size) {
            return find_centroid(v, u, total_size);
        }
    }
    return u;
}

// Optimized DFS to generate path info from the centroid
void dfs_path_gen(int u, int p, int root_node, vector<ll>& current_costs) {
    sub_parent[u] = root_node;

    // Store the path info for the current node 'u'
    path_info_map[u].costs = current_costs;
    path_info_map[u].p_sums.assign(current_costs.size() + 1, 0);
    for (size_t i = 0; i < current_costs.size(); ++i) {
        path_info_map[u].p_sums[i + 1] = path_info_map[u].p_sums[i] + current_costs[i];
    }
    
    // Recurse to children
    for (auto& edge : adj[u]) {
        int v = edge.first;
        int road_idx = edge.second;
        if (v != p && !is_removed[v]) {
            size_t original_size = current_costs.size();
            current_costs.insert(current_costs.end(), road_checkpoints[road_idx].begin(), road_checkpoints[road_idx].end());
            inplace_merge(current_costs.begin(), current_costs.begin() + original_size, current_costs.end());
            
            dfs_path_gen(v, u, root_node, current_costs);
            
            // Backtrack
            current_costs.resize(original_size);
        }
    }
}


// Calculates min silver cost to pay for k_silver checkpoints from two paths
ll calculate_min_silver(const PathInfo& s_info, const PathInfo& t_info, int k_silver) {
    if (k_silver < 0) return 0;
    if (k_silver > s_info.costs.size() + t_info.costs.size()) return INF;

    ll min_cost = INF;
    const auto& ps_s = s_info.p_sums;
    const auto& ps_t = t_info.p_sums;

    for (int i = 0; i <= s_info.costs.size(); ++i) {
        int j = k_silver - i;
        if (j >= 0 && j <= t_info.costs.size()) {
            min_cost = min(min_cost, ps_s[i] + ps_t[j]);
        }
    }
    return min_cost;
}

// The main "checker" function using Centroid Decomposition
void solve(int entry_node, vector<Query>& queries, int mid_gold, vector<bool>& results) {
    if (queries.empty()) return;

    dfs_size(entry_node, 0);
    int centroid = find_centroid(entry_node, 0, subtree_size[entry_node]);

    // Efficiently compute path info for all nodes in the component
    path_info_map.clear();
    sub_parent[centroid] = centroid;
    vector<ll> empty_costs;
    dfs_path_gen(centroid, 0, centroid, empty_costs);

    // Partition queries
    map<int, vector<Query>> sub_queries;
    vector<Query> crossing_queries;
    for (auto& q : queries) {
        if (sub_parent[q.s] == sub_parent[q.t]) {
            if (sub_parent[q.s] != centroid) {
                sub_queries[sub_parent[q.s]].push_back(q);
            } else {
                crossing_queries.push_back(q);
            }
        } else {
            crossing_queries.push_back(q);
        }
    }

    // Process queries that cross the centroid
    for (auto& q : crossing_queries) {
        const auto& s_info = path_info_map[q.s];
        const auto& t_info = path_info_map[q.t];
        
        int p_checkpoints = s_info.costs.size() + t_info.costs.size();
        int k_silver = p_checkpoints - mid_gold;

        if (k_silver < 0) {
            results[q.id] = true;
        } else {
            ll silver_needed = calculate_min_silver(s_info, t_info, k_silver);
            if (silver_needed <= q.y) {
                results[q.id] = true;
            }
        }
    }

    // Recurse on subproblems
    is_removed[centroid] = true;
    for (auto & [sub_root, qs] : sub_queries) {
        solve(sub_root, qs, mid_gold, results);
    }
}

// --- Parallel Binary Search ---
void pbs(vector<Query>& queries, int min_gold, int max_gold) {
    if (queries.empty() || min_gold > max_gold) {
        return;
    }

    int mid_gold = min_gold + (max_gold - min_gold) / 2;
    vector<Query> possible_qs, impossible_qs;

    fill(is_removed + 1, is_removed + N + 1, false);
    vector<bool> results(Q, false);
    solve(1, queries, mid_gold, results);

    for (const auto& q : queries) {
        if (results[q.id]) {
            final_ans[q.id] = mid_gold;
            possible_qs.push_back(q);
        } else {
            impossible_qs.push_back(q);
        }
    }

    pbs(possible_qs, min_gold, mid_gold - 1);
    pbs(impossible_qs, mid_gold + 1, max_gold);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> N >> M >> Q;
    for (int i = 1; i < N; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back({v, i});
        adj[v].push_back({u, i});
    }

    for (int i = 0; i < M; ++i) {
        int p;
        ll c;
        cin >> p >> c;
        road_checkpoints[p].push_back(c);
    }
    for (int i = 1; i < N; ++i) {
        sort(road_checkpoints[i].begin(), road_checkpoints[i].end());
    }

    for (int i = 0; i < Q; ++i) {
        int s, t;
        ll x, y;
        cin >> s >> t >> x >> y;
        all_queries.push_back({i, s, t, x, y});
    }

    fill(final_ans, final_ans + Q, -1);
    pbs(all_queries, 0, M); // Max possible gold spent is M

    for (int i = 0; i < Q; ++i) {
        ll gold_spent = final_ans[i];
        if (gold_spent != -1 && all_queries[i].x >= gold_spent) {
            cout << all_queries[i].x - gold_spent << "\n";
        } else {
            cout << -1 << "\n";
        }
    }

    return 0;
}

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