Submission #400364

#	Time	Username	Problem	Language	Result	Execution time	Memory
400364		12tqian	IOI Fever (JOI21_fever)	C++17	0 / 100	5067 ms	332 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 int INF = numeric_limits<int>::max();
 
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;
    map<int, vi> X;
    map<int, vi> Y;
    map<int, vi> S;
    map<int, vi> D;
    f0r(i, n) {
        X[p[i].f].pb(i);
        Y[p[i].s].pb(i);
        S[p[i].f + p[i].s].pb(i);
        D[p[i].f - p[i].s].pb(i);
    }
    each(v, X) {
        sort(all(v.s), [&](int x, int y) {
            return p[x].s < p[y].s;
        });
    }
    each(v, Y) {
        sort(all(v.s), [&](int x, int y) {
            return p[x].f < p[y].f;
        });
    }
    each(v, S) {
        sort(all(v.s), [&](int x, int y) {
            return p[x].f < p[y].f;
        });
    }
    each(v, D) {
        sort(all(v.s), [&](int x, int y) {
            return p[x].f < p[y].f;
        });
    }
    auto run_dijkstra = [&](int beg) -> int {
        priority_queue<pi, vpi, greater<pi>> pq;
        vi dist(4 * n, INF);
        vector<bool> vis(4 * n);
        
        int cnt = 0;
 
        auto ad = [&](int a, ll b) {
            cnt++;
            if (dist[a] <= b) return;
            pq.push({dist[a] = b, a});
        };
        ad(beg, 0);
        auto calc = [&](pi x, pi y) -> int {
            int nd = 2 * max(abs(x.f - y.f), abs(x.s - y.s));
            if (x.f == y.f) {
                nd = abs(x.s - y.s);
            } else if (x.s == y.s) {
                nd = abs(x.f - y.f);       
            }
            return nd;
        };
        vi active(n, 1);
        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, 4 * n) {
                if (dist[i] <= d) active[i] = 0;
            }
            { // vertical
                auto& v = X[p[u].f];
                if (d == 2) { 
                    int loc = 0;
                    while (v[loc] != u) {
                        int i = v[loc];
                        if (!active[i]) continue;
                        int nd = calc(p[v[loc]], p[u]);
                        if (nd < x.f) break;
                        ad(4 * i + 0, nd);
                        loc++;
                    }
                }
                if (d == 0) {
                    int loc = sz(v) - 1;
                    while (v[loc] != u) {
                        int i = v[loc];
                        if (!active[i]) continue;
                        int nd = calc(p[v[loc]], p[u]);
                        if (nd < x.f) break;
                        ad(4 * i + 2, nd);
                        loc--;
                    }
                }
            }
            { // horizontal
                auto& v = Y[p[u].s];
                if (d == 3) { 
                    int loc = 0;
                    while (v[loc] != u) {
                        int i = v[loc];
                        if (!active[i]) continue;
                        int nd = calc(p[v[loc]], p[u]);
                        if (nd < x.f) break;
                        ad(4 * i + 1, nd);
                        loc++;
                    }
                }
                if (d == 1) {
                    int loc = sz(v) - 1;
                    while (v[loc] != u) {
                        int i = v[loc];
                        if (!active[i]) continue;
                        int nd = calc(p[v[loc]], p[u]);
                        if (nd < x.f) break;
                        ad(4 * i + 3, nd);
                        loc--;
                    }
                }
            }
            { // sum
                auto& v = S[p[u].f + p[u].s];
                if (d == 3) { 
                    int loc = 0;
                    while (v[loc] != u) {
                        int i = v[loc];
                        if (!active[i]) continue;
                        int nd = calc(p[v[loc]], p[u]);
                        if (nd < x.f) break;
                        ad(4 * i + 2, nd);
                        loc++;
                    }
                }
                if (d == 0) {
                    int loc = 0;
                    while (v[loc] != u) {
                        int i = v[loc];
                        if (!active[i]) continue;
                        int nd = calc(p[v[loc]], p[u]);
                        if (nd < x.f) break;
                        ad(4 * i + 1, nd);
                        loc++;
                    }
                }
                if (d == 1) {
                    int loc = sz(v) - 1;
                    while (v[loc] != u) {
                        int i = v[loc];
                        if (!active[i]) continue;
                        int nd = calc(p[v[loc]], p[u]);
                        if (nd < x.f) break;
                        ad(4 * i + 0, nd);
                        loc--;
                    }
                }
                if (d == 2) {
                    int loc = sz(v) - 1;
                    while (v[loc] != u) {
                        int i = v[loc];
                        if (!active[i]) continue;
                        int nd = calc(p[v[loc]], p[u]);
                        if (nd < x.f) break;
                        ad(4 * i + 3, nd);
                        loc--;
                    }
                }
            }
            { // diff
                auto& v = D[p[u].f - p[u].s];
                if (d == 3) { 
                    int loc = 0;
                    while (v[loc] != u) {
                        int i = v[loc];
                        if (!active[i]) continue;
                        int nd = calc(p[v[loc]], p[u]);
                        if (nd < x.f) break;
                        ad(4 * i + 0, nd);
                        loc++;
                    }
                }
                if (d == 2) {
                    int loc = 0;
                    while (v[loc] != u) {
                        int i = v[loc];
                        if (!active[i]) continue;
                        int nd = calc(p[v[loc]], p[u]);
                        if (nd < x.f) break;
                        ad(4 * i + 1, nd);
                        loc++;
                    }
                }
                if (d == 0) {
                    int loc = sz(v) - 1;
                    while (v[loc] != u) {
                        int i = v[loc];
                        if (!active[i]) continue;
                        int nd = calc(p[v[loc]], p[u]);
                        if (nd < x.f) break;
                        ad(4 * i + 3, nd);
                        loc--;
                    }
                }
                if (d == 1) {
                    int loc = sz(v) - 1;
                    while (v[loc] != u) {
                        int i = v[loc];
                        if (!active[i]) continue;
                        int nd = calc(p[v[loc]], p[u]);
                        if (nd < x.f) break;
                        ad(4 * i + 2, nd);
                        loc--;
                    }
                }
            }
        }
        int res = 0;
        f0r(i, n) {
            int a = 0;
            f0r(d, 4) {
                a += (dist[4 * i + d] < INF);
            }
            assert(a <= 1);
            res += a;
        }
        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: 0 / 5
• Subtask 2: 0 / 8
• Subtask 3: 0 / 6
• Subtask 4: 0 / 6
• Subtask 5: 0 / 12
• Subtask 6: 0 / 32
• Subtask 7: 0 / 31