oj.uz

Submission #400344

# Submission time Handle Problem Language Result Execution time Memory
400344 2021-05-07T21:59:32 Z 12tqian IOI Fever (JOI21_fever) C++17
11 / 100
 1 ms 460 KB 
#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) {
            if (vis[a] && dist[a] == b) {
                return;
            }
            vis[a] = true;
            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;
        };
        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;
            }
            { // vertical
                auto& v = X[p[u].f];
                if (d == 2) { 
                    int loc = 0;
                    while (v[loc] != u) {
                        int i = v[loc];
                        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];
                        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];
                        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];
                        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];
                        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];
                        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];
                        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];
                        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];
                        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];
                        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];
                        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];
                        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;
        }
        assert(cnt <= 5 * n);
        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
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 208 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 1 ms 204 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 1 ms 204 KB Output is correct
23 Correct 1 ms 204 KB Output is correct
24 Correct 1 ms 204 KB Output is correct
25 Correct 1 ms 204 KB Output is correct
26 Correct 1 ms 204 KB Output is correct
27 Correct 1 ms 204 KB Output is correct
28 Correct 1 ms 204 KB Output is correct
29 Correct 1 ms 204 KB Output is correct
30 Correct 1 ms 204 KB Output is correct
31 Correct 1 ms 204 KB Output is correct
32 Correct 1 ms 208 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 208 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 1 ms 204 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 1 ms 204 KB Output is correct
23 Correct 1 ms 204 KB Output is correct
24 Correct 1 ms 204 KB Output is correct
25 Correct 1 ms 204 KB Output is correct
26 Correct 1 ms 204 KB Output is correct
27 Correct 1 ms 204 KB Output is correct
28 Correct 1 ms 204 KB Output is correct
29 Correct 1 ms 204 KB Output is correct
30 Correct 1 ms 204 KB Output is correct
31 Correct 1 ms 204 KB Output is correct
32 Correct 1 ms 208 KB Output is correct
33 Correct 1 ms 204 KB Output is correct
34 Correct 1 ms 204 KB Output is correct
35 Correct 1 ms 204 KB Output is correct
36 Correct 1 ms 208 KB Output is correct
37 Correct 1 ms 204 KB Output is correct
38 Runtime error 1 ms 460 KB Execution killed with signal 6
39 Halted 0 ms 0 KB -

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 208 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 1 ms 204 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 1 ms 204 KB Output is correct
23 Correct 1 ms 204 KB Output is correct
24 Correct 1 ms 204 KB Output is correct
25 Correct 1 ms 204 KB Output is correct
26 Correct 1 ms 204 KB Output is correct
27 Correct 1 ms 204 KB Output is correct
28 Correct 1 ms 204 KB Output is correct
29 Correct 1 ms 204 KB Output is correct
30 Correct 1 ms 204 KB Output is correct
31 Correct 1 ms 204 KB Output is correct
32 Correct 1 ms 208 KB Output is correct
33 Correct 1 ms 204 KB Output is correct
34 Correct 1 ms 204 KB Output is correct
35 Correct 1 ms 204 KB Output is correct
36 Correct 1 ms 208 KB Output is correct
37 Correct 1 ms 204 KB Output is correct
38 Runtime error 1 ms 460 KB Execution killed with signal 6
39 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 208 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 1 ms 204 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 1 ms 204 KB Output is correct
23 Correct 1 ms 204 KB Output is correct
24 Correct 1 ms 204 KB Output is correct
25 Correct 1 ms 204 KB Output is correct
26 Correct 1 ms 204 KB Output is correct
27 Correct 1 ms 204 KB Output is correct
28 Correct 1 ms 204 KB Output is correct
29 Correct 1 ms 204 KB Output is correct
30 Correct 1 ms 204 KB Output is correct
31 Correct 1 ms 204 KB Output is correct
32 Correct 1 ms 208 KB Output is correct
33 Correct 1 ms 204 KB Output is correct
34 Correct 1 ms 204 KB Output is correct
35 Correct 1 ms 204 KB Output is correct
36 Correct 1 ms 208 KB Output is correct
37 Correct 1 ms 204 KB Output is correct
38 Runtime error 1 ms 460 KB Execution killed with signal 6
39 Halted 0 ms 0 KB -

Subtask #6
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 208 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 1 ms 204 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 1 ms 204 KB Output is correct
23 Correct 1 ms 204 KB Output is correct
24 Correct 1 ms 204 KB Output is correct
25 Correct 1 ms 204 KB Output is correct
26 Correct 1 ms 204 KB Output is correct
27 Correct 1 ms 204 KB Output is correct
28 Correct 1 ms 204 KB Output is correct
29 Correct 1 ms 204 KB Output is correct
30 Correct 1 ms 204 KB Output is correct
31 Correct 1 ms 204 KB Output is correct
32 Correct 1 ms 208 KB Output is correct
33 Correct 1 ms 204 KB Output is correct
34 Correct 1 ms 204 KB Output is correct
35 Correct 1 ms 204 KB Output is correct
36 Correct 1 ms 208 KB Output is correct
37 Correct 1 ms 204 KB Output is correct
38 Runtime error 1 ms 460 KB Execution killed with signal 6
39 Halted 0 ms 0 KB -

Subtask #7
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 208 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 1 ms 204 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 1 ms 204 KB Output is correct
23 Correct 1 ms 204 KB Output is correct
24 Correct 1 ms 204 KB Output is correct
25 Correct 1 ms 204 KB Output is correct
26 Correct 1 ms 204 KB Output is correct
27 Correct 1 ms 204 KB Output is correct
28 Correct 1 ms 204 KB Output is correct
29 Correct 1 ms 204 KB Output is correct
30 Correct 1 ms 204 KB Output is correct
31 Correct 1 ms 204 KB Output is correct
32 Correct 1 ms 208 KB Output is correct
33 Correct 1 ms 204 KB Output is correct
34 Correct 1 ms 204 KB Output is correct
35 Correct 1 ms 204 KB Output is correct
36 Correct 1 ms 208 KB Output is correct
37 Correct 1 ms 204 KB Output is correct
38 Runtime error 1 ms 460 KB Execution killed with signal 6
39 Halted 0 ms 0 KB -