Submission #1353950

#TimeUsernameProblemLanguageResultExecution timeMemory
1353950retardeIOI Fever (JOI21_fever)C++20
25 / 100
5093 ms580 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 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 ll inf = (ll)4e18;
const bool tc = false;

// NEWS
// 0123

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

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

int n; const int mxn = 3005;
pt p[mxn];

inline void relax(set<dj> &dijk, ll dist[][4], int from, int fromdir, int to, int todir, ll edge) {
    ll curdist = dist[from][fromdir];
    if (curdist > edge) return;
    if (edge > dist[to][todir]) return;
    dijk.erase({to, todir, dist[to][todir]});
    dist[to][todir] = edge;
    dijk.insert({to, todir, dist[to][todir]});
}

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

    int fin = 0;
    for (int sd = 0; sd < 4; sd++) {
        set<dj> dijk; 
        dijk.insert({0, sd, 0});
        int ans = 0;
        static ll dist[mxn][4];

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

        string s = "NEWS\n";

        while (!dijk.empty()) {
            dj curr = *dijk.begin();
            dijk.erase(dijk.begin());
            ans++;

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

            int i = curr.i;
            int id = curr.dir;

            for (int j = 0; j < n; j++) {
                if (i == j) continue;

                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
                        if (id == 3) relax(dijk, dist, i, id, j, 0, p[i].y - p[j].y);
                    } else {
                        // i is below, so i up and j down
                        if (id == 0) relax(dijk, dist, i, id, j, 3, p[j].y - p[i].y);
                    }
                }

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

                // a is on left

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

                ll edge = llabs(p[a].x - p[b].x);
                if (p[a].y >= p[b].y) {
                    // a is above
                    // a goes down and b goes left
                    if (i == a && j == b && id == 3) relax(dijk, dist, i, id, j, 2, edge);
                    if (i == b && j == a && id == 2) relax(dijk, dist, i, id, j, 3, edge);
                    // a goes right and b goes up
                    if (i == a && j == b && id == 1) relax(dijk, dist, i, id, j, 0, edge);
                    if (i == b && j == a && id == 0) relax(dijk, dist, i, id, j, 1, edge);
                } else {
                    // a is below
                    // a goes up and b goes left
                    if (i == a && j == b && id == 0) relax(dijk, dist, i, id, j, 2, edge);
                    if (i == b && j == a && id == 2) relax(dijk, dist, i, id, j, 0, edge);
                    // a goes right and b goes down
                    if (i == a && j == b && id == 1) relax(dijk, dist, i, id, j, 3, edge);
                    if (i == b && j == a && id == 3) relax(dijk, dist, i, id, j, 1, edge);
                }
            }
        }
        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:143:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  143 |     freopen((s + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fever.cpp:144:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  144 |     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...