Submission #397926

#	Time	Username	Problem	Language	Result	Execution time	Memory
397926		phathnv	IOI Fever (JOI21_fever)	C++11	100 / 100	2161 ms	171040 KiB

fever

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int N = 1e5 + 7;
const int LOGN = 17;
const int INF = 1e9 + 7;

struct Edge{
    int v, w;
    Edge(int _v, int _w){
        v = _v;
        w = _w;
    }
};

int n, x[N], y[N], curInd, ind[N][4], f[N][3][4], nxt[N][3][4][LOGN], ord[N], dist[N * 16];
vector<Edge> adj[N * 16];
bool imp[N];

int Dist(int a, int b){
    int dx = abs(x[a] - x[b]);
    int dy = abs(y[a] - y[b]);
    assert(dx == dy || !dx || !dy);
    return (dx + dy) / 2;
}

int Calc(int s){
    for(int i = 1; i <= curInd; i++)
        dist[i] = INF;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    dist[s] = 0;
    pq.push({0, s});
    while (!pq.empty()){
        int u = pq.top().second;
        int d = pq.top().first;
        pq.pop();
        if (d != dist[u])
            continue;
        for(Edge e : adj[u])
            if (dist[e.v] > dist[u] + e.w){
                dist[e.v] = dist[u] + e.w;
                pq.push({dist[e.v], e.v});
            }
        if (u <= 4 * n){
            int dir = (u - 1) % 4;
            u = (u + 3) / 4;
            for(int type = 0; type < 3; type++){
                int v = u;
                for(int i = 16; i >= 0; i--)
                if (Dist(u, nxt[v][type][dir][i]) < d)
                    v = nxt[v][type][dir][i];
                v = nxt[v][type][dir][0];
                if (u != v && Dist(u, v) >= d && dist[f[v][type][dir]] > Dist(u, v)){
                    dist[f[v][type][dir]] = Dist(u, v);
                    pq.push({Dist(u, v), f[v][type][dir]});
                }
            }
        }
    }
    int res = 0;
    for(int i = 1; i <= n; i++)
        for(int dir = 0; dir < 4; dir++)
            res += (dist[ind[i][dir]] != INF);
    return res;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> x[i] >> y[i];
        x[i] *= 2;
        y[i] *= 2;
        ord[i] = i;
    }
    for(int i = 1; i <= n; i++)
        for(int dir = 0; dir < 4; dir++)
            ind[i][dir] = ++curInd;
    for(int i = 1; i <= n; i++)
        for(int type = 0; type < 3; type++)
            for(int dir = 0; dir < 4; dir++)
                f[i][type][dir] = ++curInd;
    for(int i = 1; i <= n; i++){
        adj[f[i][0][0]].push_back(Edge(ind[i][3], 0));
        adj[f[i][0][1]].push_back(Edge(ind[i][2], 0));
        adj[f[i][0][2]].push_back(Edge(ind[i][1], 0));
        adj[f[i][0][3]].push_back(Edge(ind[i][0], 0));
        adj[f[i][1][0]].push_back(Edge(ind[i][1], 0));
        adj[f[i][1][1]].push_back(Edge(ind[i][0], 0));
        adj[f[i][1][2]].push_back(Edge(ind[i][3], 0));
        adj[f[i][1][3]].push_back(Edge(ind[i][2], 0));
        adj[f[i][2][0]].push_back(Edge(ind[i][2], 0));
        adj[f[i][2][1]].push_back(Edge(ind[i][3], 0));
        adj[f[i][2][2]].push_back(Edge(ind[i][0], 0));
        adj[f[i][2][3]].push_back(Edge(ind[i][1], 0));
    }
    sort(ord + 1, ord + 1 + n, [&](const int &a, const int &b){
            return pair<int, int>(x[a] - y[a], x[a]) < pair<int, int>(x[b] - y[b], x[b]);
         });
    for(int l = 1; l <= n; l++){
        int r = l;
        while (r <= n && x[ord[l]] - y[ord[l]] == x[ord[r]] - y[ord[r]])
            r++;
        r--;
        for(int i = l; i <= r; i++){
            int u = ord[i];
            nxt[u][0][0][0] = (i == r? u : ord[i + 1]);
            nxt[u][0][1][0] = (i == r? u : ord[i + 1]);
            nxt[u][0][2][0] = (i == l? u : ord[i - 1]);
            nxt[u][0][3][0] = (i == l? u : ord[i - 1]);
        }
        for(int i = l; i <= r; i++){
            int u = ord[i];
            for(int j = 1; j < LOGN; j++){
                nxt[u][0][2][j] = nxt[nxt[u][0][2][j - 1]][0][2][j - 1];
                nxt[u][0][3][j] = nxt[nxt[u][0][3][j - 1]][0][3][j - 1];
            }
        }
        for(int i = r; i >= l; i--){
            int u = ord[i];
            for(int j = 1; j < LOGN; j++){
                nxt[u][0][0][j] = nxt[nxt[u][0][0][j - 1]][0][0][j - 1];
                nxt[u][0][1][j] = nxt[nxt[u][0][1][j - 1]][0][1][j - 1];
            }
        }
        for(int i = l; i < r; i++){
            int u = ord[i];
            int v = ord[i + 1];
            int d = Dist(u, v);
            adj[f[u][0][0]].push_back(Edge(f[v][0][0], d));
            adj[f[u][0][1]].push_back(Edge(f[v][0][1], d));
            adj[f[v][0][2]].push_back(Edge(f[u][0][2], d));
            adj[f[v][0][3]].push_back(Edge(f[u][0][3], d));
        }
        l = r;
    }
    sort(ord + 1, ord + 1 + n, [&](const int &a, const int &b){
            return pair<int, int>(x[a] + y[a], x[a]) < pair<int, int>(x[b] + y[b], x[b]);
         });
    for(int l = 1; l <= n; l++){
        int r = l;
        while (r <= n && x[ord[l]] + y[ord[l]] == x[ord[r]] + y[ord[r]])
            r++;
        r--;
        for(int i = l; i <= r; i++){
            int u = ord[i];
            nxt[u][1][0][0] = (i == l? u : ord[i - 1]);
            nxt[u][1][1][0] = (i == r? u : ord[i + 1]);
            nxt[u][1][2][0] = (i == r? u : ord[i + 1]);
            nxt[u][1][3][0] = (i == l? u : ord[i - 1]);
        }
        for(int i = l; i <= r; i++){
            int u = ord[i];
            for(int j = 1; j < LOGN; j++){
                nxt[u][1][0][j] = nxt[nxt[u][1][0][j - 1]][1][0][j - 1];
                nxt[u][1][3][j] = nxt[nxt[u][1][3][j - 1]][1][3][j - 1];
            }
        }
        for(int i = r; i >= l; i--){
            int u = ord[i];
            for(int j = 1; j < LOGN; j++){
                nxt[u][1][1][j] = nxt[nxt[u][1][1][j - 1]][1][1][j - 1];
                nxt[u][1][2][j] = nxt[nxt[u][1][2][j - 1]][1][2][j - 1];
            }
        }
        for(int i = l; i < r; i++){
            int u = ord[i];
            int v = ord[i + 1];
            int d = Dist(u, v);
            adj[f[v][1][0]].push_back(Edge(f[u][1][0], d));
            adj[f[u][1][1]].push_back(Edge(f[v][1][1], d));
            adj[f[u][1][2]].push_back(Edge(f[v][1][2], d));
            adj[f[v][1][3]].push_back(Edge(f[u][1][3], d));
        }
        l = r;
    }
    sort(ord + 1, ord + 1 + n, [&](const int &a, const int &b){
            return pair<int, int>(x[a], y[a]) < pair<int, int>(x[b], y[b]);
         });
    for(int l = 1; l <= n; l++){
        int r = l;
        while (r <= n && x[ord[l]] == x[ord[r]])
            r++;
        r--;
        for(int i = l; i <= r; i++){
            int u = ord[i];
            nxt[u][2][0][0] = (i == r? u : ord[i + 1]);
            nxt[u][2][2][0] = (i == l? u : ord[i - 1]);
        }
        for(int i = l; i <= r; i++){
            int u = ord[i];
            for(int j = 1; j < LOGN; j++)
                nxt[u][2][2][j] = nxt[nxt[u][2][2][j - 1]][2][2][j - 1];
        }
        for(int i = r; i >= l; i--){
            int u = ord[i];
            for(int j = 1; j < LOGN; j++)
                nxt[u][2][0][j] = nxt[nxt[u][2][0][j - 1]][2][0][j - 1];
        }
        for(int i = l; i < r; i++){
            int u = ord[i];
            int v = ord[i + 1];
            int d = Dist(u, v);
            adj[f[u][2][0]].push_back(Edge(f[v][2][0], d));
            adj[f[v][2][2]].push_back(Edge(f[u][2][2], d));
        }
        l = r;
    }
    sort(ord + 1, ord + 1 + n, [&](const int &a, const int &b){
            return pair<int, int>(y[a], x[a]) < pair<int, int>(y[b], x[b]);
         });
    for(int l = 1; l <= n; l++){
        int r = l;
        while (r <= n && y[ord[l]] == y[ord[r]])
            r++;
        r--;
        for(int i = l; i <= r; i++){
            int u = ord[i];
            nxt[u][2][1][0] = (i == r? u : ord[i + 1]);
            nxt[u][2][3][0] = (i == l? u : ord[i - 1]);
        }
        for(int i = l; i <= r; i++){
            int u = ord[i];
            for(int j = 1; j < LOGN; j++)
                nxt[u][2][3][j] = nxt[nxt[u][2][3][j - 1]][2][3][j - 1];
        }
        for(int i = r; i >= l; i--){
            int u = ord[i];
            for(int j = 1; j < LOGN; j++)
                nxt[u][2][1][j] = nxt[nxt[u][2][1][j - 1]][2][1][j - 1];
        }
        for(int i = l; i < r; i++){
            int u = ord[i];
            int v = ord[i + 1];
            int d = Dist(u, v);
            adj[f[u][2][1]].push_back(Edge(f[v][2][1], d));
            adj[f[v][2][3]].push_back(Edge(f[u][2][3], d));
        }
        l = r;
    }
    int res = 0;
    for(int dir = 0; dir < 4; dir++)
        res = max(res, Calc(ind[1][dir]));
    cout << res;
    return 0;
}

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