oj.uz

Submission #595789

# Submission time Handle Problem Language Result Execution time Memory
595789 2022-07-14T06:44:48 Z Cross_Ratio IOI Fever (JOI21_fever) C++14
6 / 100
 1 ms 340 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int,int> P;
const int INF = 1e18;
int X[100005];
int Y[100005];
int dis[100005][4];
bool vis[400005];
int simulate(int dir2, int N) {
    int i, j;
    for(i=0;i<N;i++) {
        for(j=0;j<4;j++) dis[i][j] = INF;
    }
    for(i=0;i<4*N;i++) vis[i] = false;
    dis[0][dir2] = 0;
    priority_queue<P,vector<P>,greater<P>> PQ;
    PQ.push(P(0,dir2));
    while(!PQ.empty()) {
        P k = PQ.top();
        PQ.pop();
        if(vis[k.second]) continue;
        int id = k.second / 4;
        int dir = k.second % 4;
        for(i=0;i<N;i++) {
            if(i==id) continue;
            if(abs(X[i]-X[id])!=abs(Y[i]-Y[id])) continue;
            int d = abs(X[i] - X[id]);
            for(j=0;j<4;j++) {
                int val = 2* (X[i] < X[id]) + (Y[i] < Y[id]);
                if(val==3) {
                    if(dir<=1) {
                        if(dis[i][3-dir]>d && dis[id][dir]<=d) {
                            dis[i][3-dir] = dis[id][dir] + d;
                            PQ.push(P(dis[i][3-dir],4*i+3-dir));
                        }
                    }
                }
                if(val==2) {
                    if(dir==0||dir==3) {
                        if(dis[i][(5-dir)%4]>d&&dis[id][dir]<=d) {
                            dis[i][(5-dir)%4] = dis[id][dir] + d;
                            PQ.push(P(dis[i][(5-dir)%4],4*i+(5-dir)%4));
                        }
                    }
                }
                if(val==1) {
                    if(dir==1||dir==2) {
                        if(dis[i][(5-dir)%4]>d&&dis[id][dir]<=d) {
                            dis[i][(5-dir)%4] = dis[id][dir] + d;
                            PQ.push(P(dis[i][(5-dir)%4],4*i+(5-dir)%4));
                        }
                    }
                }
                if(val==0) {
                    if(dir==2||dir==3) {
                        if(dis[i][3-dir]>d&&dis[id][dir]<=d) {
                            dis[i][3-dir] = dis[id][dir] + d;
                            PQ.push(P(dis[i][3-dir],4*i+3-dir));
                        }
                    }
                }
            }
        }
    }
    int ans = 0;
    for(i=0;i<N;i++) {
        int mi = INF;
        for(j=0;j<4;j++) mi = min(mi, dis[i][j]);
        if(mi != INF) ans++;
    }
    return ans;
}
signed main() {
    cin.sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int N;
    cin >> N;
    int i, j;
    for(i=0;i<N;i++) cin >> X[i] >> Y[i];
    int ma = 0;
    for(i=0;i<4;i++) ma = max(ma, simulate(i, N));
    cout <<ma;
}

Compilation message

fever.cpp: In function 'int main()':
fever.cpp:80:12: warning: unused variable 'j' [-Wunused-variable]
   80 |     int i, j;
      |            ^

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 0 ms 340 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 0 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 0 ms 340 KB Output is correct
20 Correct 0 ms 340 KB Output is correct
21 Correct 0 ms 340 KB Output is correct
22 Correct 0 ms 340 KB Output is correct
23 Correct 0 ms 300 KB Output is correct
24 Correct 0 ms 340 KB Output is correct
25 Correct 0 ms 224 KB Output is correct
26 Correct 0 ms 340 KB Output is correct
27 Correct 0 ms 340 KB Output is correct
28 Correct 0 ms 340 KB Output is correct
29 Incorrect 0 ms 340 KB Output isn't correct
30 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 0 ms 340 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 0 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 0 ms 340 KB Output is correct
20 Correct 0 ms 340 KB Output is correct
21 Correct 0 ms 340 KB Output is correct
22 Correct 0 ms 340 KB Output is correct
23 Correct 0 ms 300 KB Output is correct
24 Correct 0 ms 340 KB Output is correct
25 Correct 0 ms 224 KB Output is correct
26 Correct 0 ms 340 KB Output is correct
27 Correct 0 ms 340 KB Output is correct
28 Correct 0 ms 340 KB Output is correct
29 Incorrect 0 ms 340 KB Output isn't correct
30 Halted 0 ms 0 KB -

Subtask #3
6.0 / 6.0

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

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 0 ms 340 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 0 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 0 ms 340 KB Output is correct
20 Correct 0 ms 340 KB Output is correct
21 Correct 0 ms 340 KB Output is correct
22 Correct 0 ms 340 KB Output is correct
23 Correct 0 ms 300 KB Output is correct
24 Correct 0 ms 340 KB Output is correct
25 Correct 0 ms 224 KB Output is correct
26 Correct 0 ms 340 KB Output is correct
27 Correct 0 ms 340 KB Output is correct
28 Correct 0 ms 340 KB Output is correct
29 Incorrect 0 ms 340 KB Output isn't correct
30 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 0 ms 340 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 0 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 0 ms 340 KB Output is correct
20 Correct 0 ms 340 KB Output is correct
21 Correct 0 ms 340 KB Output is correct
22 Correct 0 ms 340 KB Output is correct
23 Correct 0 ms 300 KB Output is correct
24 Correct 0 ms 340 KB Output is correct
25 Correct 0 ms 224 KB Output is correct
26 Correct 0 ms 340 KB Output is correct
27 Correct 0 ms 340 KB Output is correct
28 Correct 0 ms 340 KB Output is correct
29 Incorrect 0 ms 340 KB Output isn't correct
30 Halted 0 ms 0 KB -

Subtask #6
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 0 ms 340 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 0 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 0 ms 340 KB Output is correct
20 Correct 0 ms 340 KB Output is correct
21 Correct 0 ms 340 KB Output is correct
22 Correct 0 ms 340 KB Output is correct
23 Correct 0 ms 300 KB Output is correct
24 Correct 0 ms 340 KB Output is correct
25 Correct 0 ms 224 KB Output is correct
26 Correct 0 ms 340 KB Output is correct
27 Correct 0 ms 340 KB Output is correct
28 Correct 0 ms 340 KB Output is correct
29 Incorrect 0 ms 340 KB Output isn't correct
30 Halted 0 ms 0 KB -

Subtask #7
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 0 ms 340 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 0 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 0 ms 340 KB Output is correct
20 Correct 0 ms 340 KB Output is correct
21 Correct 0 ms 340 KB Output is correct
22 Correct 0 ms 340 KB Output is correct
23 Correct 0 ms 300 KB Output is correct
24 Correct 0 ms 340 KB Output is correct
25 Correct 0 ms 224 KB Output is correct
26 Correct 0 ms 340 KB Output is correct
27 Correct 0 ms 340 KB Output is correct
28 Correct 0 ms 340 KB Output is correct
29 Incorrect 0 ms 340 KB Output isn't correct
30 Halted 0 ms 0 KB -