oj.uz

Submission #397633

# Submission time Handle Problem Language Result Execution time Memory
397633 2021-05-02T16:05:07 Z phathnv IOI Fever (JOI21_fever) C++11
11 / 100
 27 ms 37984 KB 
#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, type;
    Edge(int _v, int _w, int _type){
        v = _v;
        w = _w;
        type = _type;
    }
};

int n, x[N], y[N], curInd, ind[N][4][4], ord[N], dist[N * 16];
vector<Edge> adj[N * 16];

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 (e.type == 0){
                if (dist[u] <= e.w && dist[e.v] > e.w){
                    dist[e.v] = e.w;
                    pq.push({dist[e.v], e.v});
                }
            } else {
                if (dist[e.v] > dist[u] + e.w){
                    dist[e.v] = dist[u] + e.w;
                    pq.push({dist[e.v], e.v});
                }
            }
    }
    int res = 0;
    for(int i = 1; i <= n; i++){
        bool ok = 0;
        for(int cur = 0; cur < 4; cur++)
            for(int pre = 0; pre < 4; pre++)
                ok |= (dist[ind[i][cur][pre]] != INF);
        res += ok;
    }
    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 cur = 0; cur < 4; cur++)
            for(int pre = 0; pre < 4; pre++)
                ind[i][cur][pre] = ++curInd;
    }
    for(int i = 1; i <= n; i++)
        for(int j = i + 1; j <= n; j++)
            assert(x[i] != x[j] && y[i] != y[j]);
    for(int i = 1; i <= n; i++)
        for(int cur = 0; cur < 4; cur++)
            for(int pre = 0; pre < 4; pre++)
                adj[ind[i][cur][pre]].push_back(Edge(ind[i][cur][cur], 0, 1));
    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 k = l; k < r; k++){
            int u = ord[k];
            int v = ord[k + 1];
            int dist = (abs(x[u] - x[v]) + abs(y[u] - y[v])) / 2;
            adj[ind[u][1][1]].push_back(Edge(ind[u][1][2], dist, 0));
            adj[ind[u][1][1]].push_back(Edge(ind[v][2][1], dist, 0));
            adj[ind[v][2][2]].push_back(Edge(ind[u][1][2], dist, 0));
            adj[ind[v][2][2]].push_back(Edge(ind[v][2][1], dist, 0));
            adj[ind[u][0][0]].push_back(Edge(ind[u][0][3], dist, 0));
            adj[ind[u][0][0]].push_back(Edge(ind[v][3][0], dist, 0));
            adj[ind[v][3][3]].push_back(Edge(ind[u][0][3], dist, 0));
            adj[ind[v][3][3]].push_back(Edge(ind[v][3][0], dist, 0));

            adj[ind[v][1][2]].push_back(Edge(ind[u][1][2], dist, 1));
            adj[ind[u][2][1]].push_back(Edge(ind[v][2][1], dist, 1));
            adj[ind[v][0][3]].push_back(Edge(ind[u][0][3], dist, 1));
            adj[ind[u][3][0]].push_back(Edge(ind[u][3][0], dist, 1));
        }
        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 k = l; k < r; k++){
            int u = ord[k];
            int v = ord[k + 1];
            int dist = (abs(x[u] - x[v]) + abs(y[u] - y[v])) / 2;
            adj[ind[u][1][1]].push_back(Edge(ind[u][1][0], dist, 0));
            adj[ind[u][1][1]].push_back(Edge(ind[v][0][1], dist, 0));
            adj[ind[v][0][0]].push_back(Edge(ind[u][1][0], dist, 0));
            adj[ind[v][0][0]].push_back(Edge(ind[v][0][1], dist, 0));
            adj[ind[u][2][2]].push_back(Edge(ind[u][2][3], dist, 0));
            adj[ind[u][2][2]].push_back(Edge(ind[v][3][2], dist, 0));
            adj[ind[v][3][3]].push_back(Edge(ind[u][2][3], dist, 0));
            adj[ind[v][3][3]].push_back(Edge(ind[v][3][2], dist, 0));

            adj[ind[u][0][1]].push_back(Edge(ind[v][0][1], dist, 1));
            adj[ind[v][1][0]].push_back(Edge(ind[u][1][0], dist, 1));
            adj[ind[u][3][2]].push_back(Edge(ind[v][3][2], dist, 1));
            adj[ind[v][2][3]].push_back(Edge(ind[u][2][3], dist, 1));
        }
        l = r;
    }
    int res = 0;
    for(int dir = 0; dir < 4; dir++)
        res = max(res, Calc(ind[1][dir][dir]));
    cout << res;
    return 0;
}


/*
30
275810186 246609547
122805872 99671769
243507947 220373844
281305347 252104708
237805644 214671541
172469077 149334974
222589229 229887956
160653451 208404690
241378966 211098219
144302355 224755786
186392385 163258282
199129390 169928751
294937491 265736852
196096122 172962019
314342944 285142305
202720470 166337671
157037485 133903382
263858979 240724876
210720220 181519581
296402036 267201397
186021287 183036854
195081930 173976211
328293029 299092390
261195361 238061258
323595085 294394446
299933764 270733125
240976723 128081418
188501753 165367650
277832422 248631783
119896220 96762117
*/

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 37836 KB Output is correct
2 Correct 25 ms 37924 KB Output is correct
3 Correct 24 ms 37836 KB Output is correct
4 Correct 24 ms 37880 KB Output is correct
5 Correct 24 ms 37836 KB Output is correct
6 Correct 25 ms 37836 KB Output is correct
7 Correct 25 ms 37836 KB Output is correct
8 Correct 24 ms 37836 KB Output is correct
9 Correct 24 ms 37884 KB Output is correct
10 Correct 25 ms 37924 KB Output is correct
11 Correct 25 ms 37836 KB Output is correct
12 Correct 25 ms 37884 KB Output is correct
13 Correct 24 ms 37864 KB Output is correct
14 Correct 25 ms 37828 KB Output is correct
15 Correct 24 ms 37900 KB Output is correct
16 Correct 24 ms 37836 KB Output is correct
17 Correct 25 ms 37936 KB Output is correct
18 Correct 25 ms 37904 KB Output is correct
19 Correct 24 ms 37836 KB Output is correct
20 Correct 24 ms 37836 KB Output is correct
21 Correct 25 ms 37812 KB Output is correct
22 Correct 24 ms 37908 KB Output is correct
23 Correct 24 ms 37816 KB Output is correct
24 Correct 24 ms 37836 KB Output is correct
25 Correct 24 ms 37904 KB Output is correct
26 Correct 24 ms 37828 KB Output is correct
27 Correct 24 ms 37836 KB Output is correct
28 Correct 25 ms 37824 KB Output is correct
29 Correct 25 ms 37908 KB Output is correct
30 Correct 23 ms 37836 KB Output is correct
31 Correct 24 ms 37844 KB Output is correct
32 Correct 24 ms 37816 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 37836 KB Output is correct
2 Correct 25 ms 37924 KB Output is correct
3 Correct 24 ms 37836 KB Output is correct
4 Correct 24 ms 37880 KB Output is correct
5 Correct 24 ms 37836 KB Output is correct
6 Correct 25 ms 37836 KB Output is correct
7 Correct 25 ms 37836 KB Output is correct
8 Correct 24 ms 37836 KB Output is correct
9 Correct 24 ms 37884 KB Output is correct
10 Correct 25 ms 37924 KB Output is correct
11 Correct 25 ms 37836 KB Output is correct
12 Correct 25 ms 37884 KB Output is correct
13 Correct 24 ms 37864 KB Output is correct
14 Correct 25 ms 37828 KB Output is correct
15 Correct 24 ms 37900 KB Output is correct
16 Correct 24 ms 37836 KB Output is correct
17 Correct 25 ms 37936 KB Output is correct
18 Correct 25 ms 37904 KB Output is correct
19 Correct 24 ms 37836 KB Output is correct
20 Correct 24 ms 37836 KB Output is correct
21 Correct 25 ms 37812 KB Output is correct
22 Correct 24 ms 37908 KB Output is correct
23 Correct 24 ms 37816 KB Output is correct
24 Correct 24 ms 37836 KB Output is correct
25 Correct 24 ms 37904 KB Output is correct
26 Correct 24 ms 37828 KB Output is correct
27 Correct 24 ms 37836 KB Output is correct
28 Correct 25 ms 37824 KB Output is correct
29 Correct 25 ms 37908 KB Output is correct
30 Correct 23 ms 37836 KB Output is correct
31 Correct 24 ms 37844 KB Output is correct
32 Correct 24 ms 37816 KB Output is correct
33 Correct 25 ms 37896 KB Output is correct
34 Correct 24 ms 37836 KB Output is correct
35 Correct 25 ms 37836 KB Output is correct
36 Correct 25 ms 37840 KB Output is correct
37 Correct 25 ms 37832 KB Output is correct
38 Correct 27 ms 37800 KB Output is correct
39 Correct 24 ms 37924 KB Output is correct
40 Correct 24 ms 37936 KB Output is correct
41 Incorrect 24 ms 37836 KB Output isn't correct
42 Halted 0 ms 0 KB -

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 37964 KB Output is correct
2 Correct 25 ms 37956 KB Output is correct
3 Correct 24 ms 37964 KB Output is correct
4 Correct 24 ms 37984 KB Output is correct
5 Correct 24 ms 37880 KB Output is correct
6 Correct 24 ms 37964 KB Output is correct
7 Correct 24 ms 37880 KB Output is correct
8 Correct 24 ms 37928 KB Output is correct

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 37836 KB Output is correct
2 Correct 25 ms 37924 KB Output is correct
3 Correct 24 ms 37836 KB Output is correct
4 Correct 24 ms 37880 KB Output is correct
5 Correct 24 ms 37836 KB Output is correct
6 Correct 25 ms 37836 KB Output is correct
7 Correct 25 ms 37836 KB Output is correct
8 Correct 24 ms 37836 KB Output is correct
9 Correct 24 ms 37884 KB Output is correct
10 Correct 25 ms 37924 KB Output is correct
11 Correct 25 ms 37836 KB Output is correct
12 Correct 25 ms 37884 KB Output is correct
13 Correct 24 ms 37864 KB Output is correct
14 Correct 25 ms 37828 KB Output is correct
15 Correct 24 ms 37900 KB Output is correct
16 Correct 24 ms 37836 KB Output is correct
17 Correct 25 ms 37936 KB Output is correct
18 Correct 25 ms 37904 KB Output is correct
19 Correct 24 ms 37836 KB Output is correct
20 Correct 24 ms 37836 KB Output is correct
21 Correct 25 ms 37812 KB Output is correct
22 Correct 24 ms 37908 KB Output is correct
23 Correct 24 ms 37816 KB Output is correct
24 Correct 24 ms 37836 KB Output is correct
25 Correct 24 ms 37904 KB Output is correct
26 Correct 24 ms 37828 KB Output is correct
27 Correct 24 ms 37836 KB Output is correct
28 Correct 25 ms 37824 KB Output is correct
29 Correct 25 ms 37908 KB Output is correct
30 Correct 23 ms 37836 KB Output is correct
31 Correct 24 ms 37844 KB Output is correct
32 Correct 24 ms 37816 KB Output is correct
33 Correct 25 ms 37896 KB Output is correct
34 Correct 24 ms 37836 KB Output is correct
35 Correct 25 ms 37836 KB Output is correct
36 Correct 25 ms 37840 KB Output is correct
37 Correct 25 ms 37832 KB Output is correct
38 Correct 27 ms 37800 KB Output is correct
39 Correct 24 ms 37924 KB Output is correct
40 Correct 24 ms 37936 KB Output is correct
41 Incorrect 24 ms 37836 KB Output isn't correct
42 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 37836 KB Output is correct
2 Correct 25 ms 37924 KB Output is correct
3 Correct 24 ms 37836 KB Output is correct
4 Correct 24 ms 37880 KB Output is correct
5 Correct 24 ms 37836 KB Output is correct
6 Correct 25 ms 37836 KB Output is correct
7 Correct 25 ms 37836 KB Output is correct
8 Correct 24 ms 37836 KB Output is correct
9 Correct 24 ms 37884 KB Output is correct
10 Correct 25 ms 37924 KB Output is correct
11 Correct 25 ms 37836 KB Output is correct
12 Correct 25 ms 37884 KB Output is correct
13 Correct 24 ms 37864 KB Output is correct
14 Correct 25 ms 37828 KB Output is correct
15 Correct 24 ms 37900 KB Output is correct
16 Correct 24 ms 37836 KB Output is correct
17 Correct 25 ms 37936 KB Output is correct
18 Correct 25 ms 37904 KB Output is correct
19 Correct 24 ms 37836 KB Output is correct
20 Correct 24 ms 37836 KB Output is correct
21 Correct 25 ms 37812 KB Output is correct
22 Correct 24 ms 37908 KB Output is correct
23 Correct 24 ms 37816 KB Output is correct
24 Correct 24 ms 37836 KB Output is correct
25 Correct 24 ms 37904 KB Output is correct
26 Correct 24 ms 37828 KB Output is correct
27 Correct 24 ms 37836 KB Output is correct
28 Correct 25 ms 37824 KB Output is correct
29 Correct 25 ms 37908 KB Output is correct
30 Correct 23 ms 37836 KB Output is correct
31 Correct 24 ms 37844 KB Output is correct
32 Correct 24 ms 37816 KB Output is correct
33 Correct 25 ms 37896 KB Output is correct
34 Correct 24 ms 37836 KB Output is correct
35 Correct 25 ms 37836 KB Output is correct
36 Correct 25 ms 37840 KB Output is correct
37 Correct 25 ms 37832 KB Output is correct
38 Correct 27 ms 37800 KB Output is correct
39 Correct 24 ms 37924 KB Output is correct
40 Correct 24 ms 37936 KB Output is correct
41 Incorrect 24 ms 37836 KB Output isn't correct
42 Halted 0 ms 0 KB -

Subtask #6
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 37836 KB Output is correct
2 Correct 25 ms 37924 KB Output is correct
3 Correct 24 ms 37836 KB Output is correct
4 Correct 24 ms 37880 KB Output is correct
5 Correct 24 ms 37836 KB Output is correct
6 Correct 25 ms 37836 KB Output is correct
7 Correct 25 ms 37836 KB Output is correct
8 Correct 24 ms 37836 KB Output is correct
9 Correct 24 ms 37884 KB Output is correct
10 Correct 25 ms 37924 KB Output is correct
11 Correct 25 ms 37836 KB Output is correct
12 Correct 25 ms 37884 KB Output is correct
13 Correct 24 ms 37864 KB Output is correct
14 Correct 25 ms 37828 KB Output is correct
15 Correct 24 ms 37900 KB Output is correct
16 Correct 24 ms 37836 KB Output is correct
17 Correct 25 ms 37936 KB Output is correct
18 Correct 25 ms 37904 KB Output is correct
19 Correct 24 ms 37836 KB Output is correct
20 Correct 24 ms 37836 KB Output is correct
21 Correct 25 ms 37812 KB Output is correct
22 Correct 24 ms 37908 KB Output is correct
23 Correct 24 ms 37816 KB Output is correct
24 Correct 24 ms 37836 KB Output is correct
25 Correct 24 ms 37904 KB Output is correct
26 Correct 24 ms 37828 KB Output is correct
27 Correct 24 ms 37836 KB Output is correct
28 Correct 25 ms 37824 KB Output is correct
29 Correct 25 ms 37908 KB Output is correct
30 Correct 23 ms 37836 KB Output is correct
31 Correct 24 ms 37844 KB Output is correct
32 Correct 24 ms 37816 KB Output is correct
33 Correct 25 ms 37896 KB Output is correct
34 Correct 24 ms 37836 KB Output is correct
35 Correct 25 ms 37836 KB Output is correct
36 Correct 25 ms 37840 KB Output is correct
37 Correct 25 ms 37832 KB Output is correct
38 Correct 27 ms 37800 KB Output is correct
39 Correct 24 ms 37924 KB Output is correct
40 Correct 24 ms 37936 KB Output is correct
41 Incorrect 24 ms 37836 KB Output isn't correct
42 Halted 0 ms 0 KB -

Subtask #7
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 37836 KB Output is correct
2 Correct 25 ms 37924 KB Output is correct
3 Correct 24 ms 37836 KB Output is correct
4 Correct 24 ms 37880 KB Output is correct
5 Correct 24 ms 37836 KB Output is correct
6 Correct 25 ms 37836 KB Output is correct
7 Correct 25 ms 37836 KB Output is correct
8 Correct 24 ms 37836 KB Output is correct
9 Correct 24 ms 37884 KB Output is correct
10 Correct 25 ms 37924 KB Output is correct
11 Correct 25 ms 37836 KB Output is correct
12 Correct 25 ms 37884 KB Output is correct
13 Correct 24 ms 37864 KB Output is correct
14 Correct 25 ms 37828 KB Output is correct
15 Correct 24 ms 37900 KB Output is correct
16 Correct 24 ms 37836 KB Output is correct
17 Correct 25 ms 37936 KB Output is correct
18 Correct 25 ms 37904 KB Output is correct
19 Correct 24 ms 37836 KB Output is correct
20 Correct 24 ms 37836 KB Output is correct
21 Correct 25 ms 37812 KB Output is correct
22 Correct 24 ms 37908 KB Output is correct
23 Correct 24 ms 37816 KB Output is correct
24 Correct 24 ms 37836 KB Output is correct
25 Correct 24 ms 37904 KB Output is correct
26 Correct 24 ms 37828 KB Output is correct
27 Correct 24 ms 37836 KB Output is correct
28 Correct 25 ms 37824 KB Output is correct
29 Correct 25 ms 37908 KB Output is correct
30 Correct 23 ms 37836 KB Output is correct
31 Correct 24 ms 37844 KB Output is correct
32 Correct 24 ms 37816 KB Output is correct
33 Correct 25 ms 37896 KB Output is correct
34 Correct 24 ms 37836 KB Output is correct
35 Correct 25 ms 37836 KB Output is correct
36 Correct 25 ms 37840 KB Output is correct
37 Correct 25 ms 37832 KB Output is correct
38 Correct 27 ms 37800 KB Output is correct
39 Correct 24 ms 37924 KB Output is correct
40 Correct 24 ms 37936 KB Output is correct
41 Incorrect 24 ms 37836 KB Output isn't correct
42 Halted 0 ms 0 KB -