Submission #1185242

#	Time	Username	Problem	Language	Result	Execution time	Memory
1185242		jerzyk	Coin Collecting (JOI19_ho_t4)	C++20	37 / 100	814 ms	31888 KiB

joi2019_ho_t4

#include <bits/stdc++.h>

using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;
const ll I = 1'000'000'000'000'000'000LL;
const int II = 2'000'000'000;
const ll M = 1'000'000'007LL;
const int N = 1<<17;
pair<int, int> co[N];
vector<int> pos[2];
int tab[N];

map<pair<int, int>, ll> dis;
map<pair<int, int>, ll>::iterator it;

ll A(int a, int b)
{
    if(a > b) return a - b;
    return b - a;
}

ll Dijsktra()
{
    priority_queue<pair<ll, pair<int, int> >> q;
    int n = pos[0].size(), m = pos[1].size();
    dis[make_pair(0, 0)] = 0;
    q.push(make_pair(0, make_pair(0, 0)));
    while(q.size() > 0)
    {
        int a = q.top().nd.st, b = q.top().nd.nd;
        ll d = -q.top().st, o;
        q.pop();
        int p = (a + b) / 2 + 1;
        if(dis[make_pair(a, b)] != d) continue;
        // cout << "\nD: " << a << " " << b << " " << d << "\n";
        if(a == n && b == m) return d;
        if(a < n && b < m)
        {
            o = d + A(pos[0][a], p) + A(p, pos[1][b]);
            if(dis.find(make_pair(a + 1, b + 1)) == dis.end()) dis[make_pair(a + 1, b + 1)] = I;
            it = dis.find(make_pair(a + 1, b + 1));
            if((*it).nd > o)
            {
                // cout << "E: " << a + 1 << " " << b + 1 << " " << o << "\n";
                (*it).nd = o;
                q.push(make_pair(-o, make_pair(a + 1, b + 1)));
            }
        }
        if(a < n - 1)
        {
            o = d + A(pos[0][a], p) + A(pos[0][a + 1], p) + 1LL;
            if(dis.find(make_pair(a + 2, b)) == dis.end()) dis[make_pair(a + 2, b)] = I;
            it = dis.find(make_pair(a + 2, b));
            if((*it).nd > o)
            {
                // cout << "E: " << a + 2 << " " << b << " " << o << "\n";
                (*it).nd = o;
                q.push(make_pair(-o, make_pair(a + 2, b)));
            }
        }
        if(b < m - 1)
        {
            o = d + A(pos[1][b], p) + A(pos[1][b + 1], p) + 1LL;
            if(dis.find(make_pair(a, b + 2)) == dis.end()) dis[make_pair(a, b + 2)] = I;
            it = dis.find(make_pair(a, b + 2));
            if((*it).nd > o)
            {
                // cout << "E: " << a << " " << b + 2 << " " << o << "\n";
                (*it).nd = o;
                q.push(make_pair(-o, make_pair(a, b + 2)));
            }
        }
    }
    return -1LL;
}

void Solve()
{
    int n;
    ll answer = 0LL;
    cin >> n;
    for(int i = 1; i <= 2 * n; ++i)
    {
        cin >> co[i].st >> co[i].nd;
        if(co[i].st < 1)
            {answer += 1 - co[i].st; co[i].st = 1;}
        if(co[i].st > n)
            {answer += co[i].st - n; co[i].st = n;}
        if(co[i].nd < 1)
            {answer += 1 - co[i].nd; co[i].nd = 1;}
        if(co[i].nd > 2)
            {answer += co[i].nd - 2; co[i].nd = 2;}
        // cout << "I: " << co[i].st << " " << co[i].nd << "\n";
        pos[co[i].nd - 1].pb(co[i].st);
    }
    sort(pos[0].begin(), pos[0].end());
    sort(pos[1].begin(), pos[1].end());
    ll ans = Dijsktra();
    ans += answer;
    cout << ans << "\n";
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    //int t; cin >> t;
    //while(t--)
        Solve();

    return 0;
}

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