Submission #400329

#	Time	Username	Problem	Language	Result	Execution time	Memory
400329		12tqian	IOI Fever (JOI21_fever)	C++17	37 / 100	5037 ms	6472 KiB

fever

#include <bits/stdc++.h>

using namespace std;

#define f1r(i, a, b) for (int i = a; i < b; ++i)
#define f0r(i, a) f1r(i, 0, a)
#define each(t, a) for (auto& t : a)

#define mp make_pair
#define f first
#define s second
#define pb push_back
#define eb emplace_back
#define sz(x) (int)(x).size()
#define all(x) begin(x), end(x)

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;

template <class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template <class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }

const ll INF = 1e18;

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int n; cin >> n;
    vpi p(n);
    f0r(i, n) cin >> p[i].f >> p[i].s;
    auto run_dijkstra = [&](int beg) -> int {
        typedef pair<ll, int> T;
        priority_queue<T, vector<T>, greater<T>> pq;
        vl dist(4 * n, INF);
        vector<bool> vis(4 * n);
        int cnt = 0;
        auto ad = [&](int a, ll b) {
            if (dist[a] <= b) return;
            if (vis[a] && dist[a] == b) {
                return;
            }
            vis[a] = true;
            cnt++;
            pq.push({dist[a] = b, a});
        };
        ad(beg, 0);
        while (!pq.empty()) {
            auto x = pq.top();
            pq.pop();
            int u = x.s / 4;
            int d = x.s % 4;
            if (dist[4 * u + d] < x.f) {
                continue;
            }
            f0r(i, n) {
                if (i == u) continue;
                ll nd = 2 * max(abs(p[i].f - p[u].f), abs(p[i].s - p[u].s));
                if (p[i].f == p[u].f) {
                    nd = abs(p[i].s - p[u].s);
                } else if (p[i].s == p[u].s) {
                    nd = abs(p[i].f - p[u].f);       
                }
                if (nd < x.f) continue;
                if (p[i].f == p[u].f) {
                    if (p[i].s < p[u].s) {
                        if (d == 2) {
                            ad(4 * i + 0, nd);    
                        }
                    } else {
                        if (d == 0) {
                            ad(4 * i + 2, nd);
                        }
                    }
                } else if (p[i].s == p[u].s) {
                    if (p[i].f < p[u].f) {
                        if (d == 3) {
                            ad(4 * i + 1, nd);
                        }
                    } else {
                        if (d == 1) {
                            ad(4 * i + 3, nd);
                        }
                    }
                } else if (p[i].f + p[i].s == p[u].f + p[u].s) {
                    if (p[i].f < p[u].f) {
                        if (d == 3) {
                            ad(4 * i + 2, nd);
                        } else if (d == 0) {
                            ad(4 * i + 1, nd);
                        }
                    } else {
                        if (d == 2) {
                            ad(4 * i + 3, nd);
                        } else if (d == 1) {
                            ad(4 * i + 0, nd);
                        }
                    }
                } else if (p[i].f - p[i].s == p[u].f - p[u].s) {
                    if (p[i].f < p[u].f) {
                        if (d == 3) {
                            ad(4 * i + 0, nd);
                        } else if (d == 2) {
                            ad(4 * i + 1, nd);
                        }
                    } else {
                        if (d == 0) {
                            ad(4 * i + 3, nd);
                        } else if (d == 1) {
                            ad(4 * i + 2, nd);
                        }
                    }
                }
            }
        }
        int res = 0;
        f0r(i, n) {
            int a = 0;
            f0r(d, 4) {
                a += (dist[4 * i + d] < INF);
            }
            assert(a <= 1);
            res += a;
        }
        assert(cnt <= n * 5);
        return res;
    };
    int ans = 0;
    f0r(d, 4) {
        ckmax(ans, run_dijkstra(d));
    }
    cout << ans << '\n';

    return 0;
}

/**
 * first try n^2 bash
 * 0 - up
 * 1 - right
 * 2 - down
 * 3 - left
 */

• Subtask 1: 5 / 5
• Subtask 2: 8 / 8
• Subtask 3: 6 / 6
• Subtask 4: 6 / 6
• Subtask 5: 12 / 12
• Subtask 6: 0 / 32
• Subtask 7: 0 / 31