Submission #1148065

#	Time	Username	Problem	Language	Result	Execution time	Memory
1148065		tito_daynor	Coin Collecting (JOI19_ho_t4)	C++17	0 / 100	1099 ms	80016 KiB

joi2019_ho_t4

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;

class Solution {
private:
    vector<pll> getNeighbors(pll pos) {
        vector<pll> neighbors = {
            {pos.first + 1, pos.second},
            {pos.first - 1, pos.second},
            {pos.first, pos.second + 1},
            {pos.first, pos.second - 1}
        };
        return neighbors;
    }
    
    ll bfs(pll start, pll end) {
        if (start == end) return 0;
        
        set<pll> visited;
        queue<pair<pll, ll>> q;
        
        visited.insert(start);
        q.push({start, 0});
        
        while (!q.empty()) {
            auto [pos, dist] = q.front();
            q.pop();
            
            if (pos == end) {
                return dist;
            }
            
            for (auto next : getNeighbors(pos)) {
                if (visited.find(next) == visited.end()) {
                    visited.insert(next);
                    q.push({next, dist + 1});
                }
            }
        }
        
        return LLONG_MAX;
    }
    
public:
    ll getMinimumOperations(ll N, vector<pll>& coins) {
        // Generate target positions
        vector<pll> targets;
        for (ll x = 1; x <= N; x++) {
            for (ll y = 1; y <= 2; y++) {
                targets.push_back({x, y});
            }
        }
        
        ll total_ops = 0;
        set<ll> used_coins;
        
        for (auto target : targets) {
            ll min_dist = LLONG_MAX;
            ll best_coin = -1;
            
            for (ll i = 0; i < coins.size(); i++) {
                if (used_coins.find(i) == used_coins.end()) {
                    ll dist = bfs(coins[i], target);
                    if (dist < min_dist) {
                        min_dist = dist;
                        best_coin = i;
                    }
                }
            }
            
            total_ops += min_dist;
            used_coins.insert(best_coin);
        }
        
        return total_ops;
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    ll N;
    cin >> N;
    
    vector<pll> coins(2*N);
    for (ll i = 0; i < 2*N; i++) {
        cin >> coins[i].first >> coins[i].second;
    }
    
    Solution solution;
    cout << solution.getMinimumOperations(N, coins) << "\n";
    
    return 0;
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 29
• Subtask 3: 0 / 63