Submission #1353946

#TimeUsernameProblemLanguageResultExecution timeMemory
1353946retardeIOI Fever (JOI21_fever)C++20
25 / 100
630 ms589824 KiB
#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define pf push_front
#define mp make_pair
#define fi first
#define se second
#define int long long
#define all(x) (x).begin(), (x).end()

typedef long double ld;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<bool> vb;
typedef vector<vector<int>> vvi;
typedef vector<vector<bool>> vvb;
typedef vector<vector<ll>> vvll;
typedef vector<string> vs;
typedef vector<vector<string>> vvs;
typedef vector<char> vc;
typedef vector<vector<char>> vvc;
typedef map<int, int> mii;
typedef unordered_map<int, int> umii;

const int mod = 1e9 + 7;
const int inf = INTMAX_MAX;
const bool tc = false;

// NEWS
// 0123

struct pt {
    int x, y, i;
};

struct dj {
    int x, y, i, dir, dist;
    bool operator<(const dj &other) const {
        if (dist != other.dist) return dist > other.dist;
        else if (x != other.x) return x > other.x;
        else return y > other.y;
    }
};

int n; const int mxn = 3005;
pt p[mxn]; vector<pair<pii, int>> adj[mxn][4];

inline void solve() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> p[i].x >> p[i].y;
        p[i].i = i;
    }
    
    for (int _1 = 0; _1 < n; _1++) {
        for (int _2 = _1 + 1; _2 < n; _2++) {
            int i = _1, j = _2;

            if (p[i].x == p[j].x) {
                // same x
                if (p[i].y > p[j].y) {
                    // i is above, so i down and j up
                    adj[i][3].pb({{j, 0}, p[i].y - p[j].y});
                    adj[j][0].pb({{i, 3}, p[i].y - p[j].y});
                } else {
                    // i is below, so i up and j down
                    adj[i][0].pb({{j, 3}, p[j].y - p[i].y});
                    adj[j][3].pb({{i, 0}, p[j].y - p[i].y});
                }
            }

            // not in line

            if (p[i].x >= p[j].x) swap(i, j);

            // i is on left

            if (abs(p[i].x - p[j].x) != abs(p[j].y - p[i].y)) {
                // cout << i+1 << " " << j+1 << " not comp\n";
                continue;
            }

            int dist = abs(p[i].x - p[j].x);
            if (p[i].y >= p[j].y) {
                // i is above
                // i goes down and j goes left
                adj[i][3].pb({{j, 2}, dist});
                adj[j][2].pb({{i, 3}, dist});
                // i goes right and j goes up
                adj[i][1].pb({{j, 0}, dist});
                adj[j][0].pb({{i, 1}, dist});
            } else {
                // i is below
                // i goes up and j goes left
                adj[i][0].pb({{j, 2}, dist});
                adj[j][2].pb({{i, 0}, dist});
                // i goes right and j goes down
                adj[i][1].pb({{j, 3}, dist});
                adj[j][3].pb({{i, 1}, dist});
            }
        }
    }

    int fin = 0;
    for (int sd = 0; sd < 4; sd++) {
        // x y i dir dist
        priority_queue<dj> dijk; dijk.push({p[0].x, p[0].y, 0, sd, 0});
        int ans = 0;
        static int dist[mxn][4];

        fill(&dist[0][0], &dist[0][0] + mxn * 4, (int)1e18);
        dist[0][sd] = 0;

        while (!dijk.empty()) {
            dj curr = dijk.top();
            dijk.pop();
            if (curr.dist != dist[curr.i][curr.dir]) continue;
            ans++;
            int curdist = curr.dist;

            // cout << "Seeing " << curr.i+1 << " in " << s[curr.dir] << '\n';
            // cout << "Currdist " << curdist << '\n';

            for (auto &nxt : adj[curr.i][curr.dir]) {
                int j = nxt.fi.fi; int jd = nxt.fi.se; int edge = nxt.se;
                // cout << "Neighbour " << j+1 << " in " << s[jd] << " will reach at " << edge << '\n';
                if (curdist > edge) {
                    // cout << "Too late\n";
                    continue;
                }
                if (edge > dist[j][jd]) {
                    // cout << "Useless\n";
                    continue;
                }
                dist[j][jd] = edge;
                dijk.push({p[j].x, p[j].y, p[j].i, jd, dist[j][jd]});
            }
        }
        fin = max(fin, ans);
    }

    cout << fin << '\n';
}

void setIO(string s) {
    freopen((s + ".in").c_str(), "r", stdin);
    freopen((s + ".out").c_str(), "w", stdout);
}

signed main() {
    ios::sync_with_stdio(false);
    cout.tie(0);
    cin.tie(0);
    //setIO();

    int t = 1;
    if (tc) {
        cin >> t;
    }

    while (t--) {
        solve();
    }
}

Compilation message (stderr)

fever.cpp: In function 'void setIO(std::string)':
fever.cpp:150:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  150 |     freopen((s + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fever.cpp:151:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  151 |     freopen((s + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...