Submission #397649

#	Time	Username	Problem	Language	Result	Execution time	Memory
397649		phathnv	IOI Fever (JOI21_fever)	C++11	0 / 100	20 ms	28492 KiB

fever

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

typedef long long ll;

const int N = 1e5 + 7;
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][2][4], nxt[N][2][4], ord[N], dist[N * 12];
vector<Edge> adj[N * 12];
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);
    return dx;
}

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 < 2; type++){
                int v = u;
                while (nxt[v][type][dir] != v && Dist(u, v) < d)
                    v = nxt[v][type][dir];
                if (u == v)
                    v = nxt[v][type][dir];
                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);
    freopen("inp.txt", "r", stdin);
    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 < 2; 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));
    }
    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] = (i == r? u : ord[i + 1]);
            nxt[u][0][1] = (i == r? u : ord[i + 1]);
            nxt[u][0][2] = (i == l? u : ord[i - 1]);
            nxt[u][0][3] = (i == l? u : ord[i - 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] = (i == l? u : ord[i - 1]);
            nxt[u][1][1] = (i == r? u : ord[i + 1]);
            nxt[u][1][2] = (i == r? u : ord[i + 1]);
            nxt[u][1][3] = (i == l? u : ord[i - 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;
    }

    int res = 0;
    for(int dir = 0; dir < 4; dir++)
        res = max(res, Calc(ind[1][dir]));
    cout << res;

    return 0;
}

Compilation message (stderr)

fever.cpp: In function 'int main()':
fever.cpp:71:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   71 |     freopen("inp.txt", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• 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