oj.uz

Submission #545432

# Submission time Handle Problem Language Result Execution time Memory
545432 2022-04-04T13:59:03 Z Dan13llljws IOI Fever (JOI21_fever) C++14
25 / 100
 428 ms 596 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int read(){int s=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){s=(s<<3)+(s<<1)+ch-'0',ch=getchar();}return s*f;}
#define re read()
const int mod = 1e9 + 7, MM = 3005;
int n, ans, x[MM], y[MM], vis[MM], d[4][MM];
int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
int solve(int i, int di, int j, int dj){
    // (x[i], y[i]) + t(dx[di], dy[di]) == (x[j], y[j]) + t(dx[dj], dy[dj]);
    // x[i] + t(dx[di]) == x[j] + t(dx[dj])
    // y[i] + t[dy[di]) == y[j] + t(dy[dj])
    // (x[i] - x[j]) / (dx[dj] - dx[di]) = t
    if (dx[dj] == dx[di]){
        if (x[i] != x[j] || (y[i] - y[j]) % (dy[dj] - dy[di])) return -1;
        return (y[i] - y[j]) / (dy[dj] - dy[di]);
    } else if (dy[dj] == dy[di]){
        if (y[i] != y[j] || (x[i] - x[j]) % (dx[dj] - dx[di])) return -1;
        return (x[i] - x[j]) / (dx[dj] - dx[di]);
    } else {
        if ((x[i] - x[j]) % (dx[dj] - dx[di]) || (y[i] - y[j]) % (dy[dj] - dy[di])) return -1;
        int t = (x[i] - x[j]) / (dx[dj] - dx[di]), s = (y[i] - y[j]) / (dy[dj] - dy[di]);
//         cout << t<< ' '<< s << endl;
        return t == s ? t : -1;
    }
}
int main(){
    n = re;
    for (int i = 1; i <= n; i++) x[i] = re, y[i] = re;
//     cout<< solve(6, 1, 10, 3);
    for (int d1 = 0; d1 < 4; d1++){
        memset(d, 0x3f, sizeof d), memset(vis, 0, sizeof vis);
        int cur = 0; d[d1][1] = 0;
        for (int i = 1; i <= n; i++){
            int u = -1, dir, mint = 1e9;
            for (int j = 1; j <= n; j++)
                for (int di = 0; di < 4; di++)
                    if (!vis[j] && d[di][j] < mint) mint = d[di][j], u = j, dir = di;
            if (u == -1) break;
            vis[u] = 1, cur++;
//             cout << u << ' ' << mint << ' ' << dir << endl;
            for (int v = 1; v <= n; v++)
                if (!vis[v])
                    for (int di = 0; di < 4; di++){
                        if (di == dir) continue;
//                         cout << v <<' ' << di << endl;
                        int t = solve(u, dir, v, di);
//                         cout << t << endl;
                        if (t >= 0 && t >= mint) d[di][v] = min(d[di][v], t);
                    }
        } ans = max(ans, cur);
    } printf("%d\n", ans);
}

Subtask #1
5.0 / 5.0

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

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 308 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 308 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 304 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 260 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 0 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 312 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 0 ms 304 KB Output is correct
22 Correct 1 ms 304 KB Output is correct
23 Correct 1 ms 308 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 1 ms 304 KB Output is correct
26 Correct 0 ms 340 KB Output is correct
27 Correct 0 ms 340 KB Output is correct
28 Correct 1 ms 308 KB Output is correct
29 Correct 0 ms 340 KB Output is correct
30 Correct 0 ms 304 KB Output is correct
31 Correct 0 ms 304 KB Output is correct
32 Correct 0 ms 340 KB Output is correct
33 Correct 1 ms 340 KB Output is correct
34 Correct 1 ms 312 KB Output is correct
35 Correct 1 ms 340 KB Output is correct
36 Correct 1 ms 312 KB Output is correct
37 Correct 1 ms 312 KB Output is correct
38 Correct 1 ms 340 KB Output is correct
39 Correct 1 ms 340 KB Output is correct
40 Correct 1 ms 340 KB Output is correct
41 Correct 1 ms 340 KB Output is correct
42 Correct 1 ms 340 KB Output is correct
43 Correct 1 ms 308 KB Output is correct
44 Correct 1 ms 340 KB Output is correct
45 Correct 0 ms 340 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 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 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 308 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 308 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 304 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 260 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 0 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 312 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 0 ms 304 KB Output is correct
22 Correct 1 ms 304 KB Output is correct
23 Correct 1 ms 308 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 1 ms 304 KB Output is correct
26 Correct 0 ms 340 KB Output is correct
27 Correct 0 ms 340 KB Output is correct
28 Correct 1 ms 308 KB Output is correct
29 Correct 0 ms 340 KB Output is correct
30 Correct 0 ms 304 KB Output is correct
31 Correct 0 ms 304 KB Output is correct
32 Correct 0 ms 340 KB Output is correct
33 Correct 1 ms 340 KB Output is correct
34 Correct 1 ms 312 KB Output is correct
35 Correct 1 ms 340 KB Output is correct
36 Correct 1 ms 312 KB Output is correct
37 Correct 1 ms 312 KB Output is correct
38 Correct 1 ms 340 KB Output is correct
39 Correct 1 ms 340 KB Output is correct
40 Correct 1 ms 340 KB Output is correct
41 Correct 1 ms 340 KB Output is correct
42 Correct 1 ms 340 KB Output is correct
43 Correct 1 ms 308 KB Output is correct
44 Correct 1 ms 340 KB Output is correct
45 Correct 0 ms 340 KB Output is correct
46 Correct 0 ms 340 KB Output is correct
47 Correct 1 ms 340 KB Output is correct
48 Correct 1 ms 340 KB Output is correct
49 Correct 0 ms 340 KB Output is correct
50 Correct 0 ms 340 KB Output is correct
51 Correct 1 ms 340 KB Output is correct
52 Correct 1 ms 340 KB Output is correct
53 Correct 1 ms 340 KB Output is correct
54 Correct 0 ms 340 KB Output is correct
55 Correct 1 ms 340 KB Output is correct
56 Correct 1 ms 340 KB Output is correct
57 Correct 1 ms 340 KB Output is correct
58 Correct 2 ms 340 KB Output is correct
59 Correct 1 ms 380 KB Output is correct
60 Correct 1 ms 340 KB Output is correct
61 Correct 1 ms 340 KB Output is correct
62 Correct 1 ms 340 KB Output is correct
63 Correct 1 ms 340 KB Output is correct
64 Correct 1 ms 340 KB Output is correct
65 Correct 1 ms 312 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 308 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 308 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 304 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 260 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 0 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 312 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 0 ms 304 KB Output is correct
22 Correct 1 ms 304 KB Output is correct
23 Correct 1 ms 308 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 1 ms 304 KB Output is correct
26 Correct 0 ms 340 KB Output is correct
27 Correct 0 ms 340 KB Output is correct
28 Correct 1 ms 308 KB Output is correct
29 Correct 0 ms 340 KB Output is correct
30 Correct 0 ms 304 KB Output is correct
31 Correct 0 ms 304 KB Output is correct
32 Correct 0 ms 340 KB Output is correct
33 Correct 1 ms 340 KB Output is correct
34 Correct 1 ms 312 KB Output is correct
35 Correct 1 ms 340 KB Output is correct
36 Correct 1 ms 312 KB Output is correct
37 Correct 1 ms 312 KB Output is correct
38 Correct 1 ms 340 KB Output is correct
39 Correct 1 ms 340 KB Output is correct
40 Correct 1 ms 340 KB Output is correct
41 Correct 1 ms 340 KB Output is correct
42 Correct 1 ms 340 KB Output is correct
43 Correct 1 ms 308 KB Output is correct
44 Correct 1 ms 340 KB Output is correct
45 Correct 0 ms 340 KB Output is correct
46 Correct 0 ms 340 KB Output is correct
47 Correct 1 ms 340 KB Output is correct
48 Correct 1 ms 340 KB Output is correct
49 Correct 0 ms 340 KB Output is correct
50 Correct 0 ms 340 KB Output is correct
51 Correct 1 ms 340 KB Output is correct
52 Correct 1 ms 340 KB Output is correct
53 Correct 1 ms 340 KB Output is correct
54 Correct 0 ms 340 KB Output is correct
55 Correct 1 ms 340 KB Output is correct
56 Correct 1 ms 340 KB Output is correct
57 Correct 1 ms 340 KB Output is correct
58 Correct 2 ms 340 KB Output is correct
59 Correct 1 ms 380 KB Output is correct
60 Correct 1 ms 340 KB Output is correct
61 Correct 1 ms 340 KB Output is correct
62 Correct 1 ms 340 KB Output is correct
63 Correct 1 ms 340 KB Output is correct
64 Correct 1 ms 340 KB Output is correct
65 Correct 1 ms 312 KB Output is correct
66 Correct 1 ms 340 KB Output is correct
67 Correct 1 ms 356 KB Output is correct
68 Correct 2 ms 328 KB Output is correct
69 Incorrect 428 ms 384 KB Output isn't correct
70 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 308 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 308 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 304 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 260 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 0 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 312 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 0 ms 304 KB Output is correct
22 Correct 1 ms 304 KB Output is correct
23 Correct 1 ms 308 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 1 ms 304 KB Output is correct
26 Correct 0 ms 340 KB Output is correct
27 Correct 0 ms 340 KB Output is correct
28 Correct 1 ms 308 KB Output is correct
29 Correct 0 ms 340 KB Output is correct
30 Correct 0 ms 304 KB Output is correct
31 Correct 0 ms 304 KB Output is correct
32 Correct 0 ms 340 KB Output is correct
33 Correct 1 ms 340 KB Output is correct
34 Correct 1 ms 312 KB Output is correct
35 Correct 1 ms 340 KB Output is correct
36 Correct 1 ms 312 KB Output is correct
37 Correct 1 ms 312 KB Output is correct
38 Correct 1 ms 340 KB Output is correct
39 Correct 1 ms 340 KB Output is correct
40 Correct 1 ms 340 KB Output is correct
41 Correct 1 ms 340 KB Output is correct
42 Correct 1 ms 340 KB Output is correct
43 Correct 1 ms 308 KB Output is correct
44 Correct 1 ms 340 KB Output is correct
45 Correct 0 ms 340 KB Output is correct
46 Correct 0 ms 340 KB Output is correct
47 Correct 1 ms 340 KB Output is correct
48 Correct 1 ms 340 KB Output is correct
49 Correct 0 ms 340 KB Output is correct
50 Correct 0 ms 340 KB Output is correct
51 Correct 1 ms 340 KB Output is correct
52 Correct 1 ms 340 KB Output is correct
53 Correct 1 ms 340 KB Output is correct
54 Correct 0 ms 340 KB Output is correct
55 Correct 1 ms 340 KB Output is correct
56 Correct 1 ms 340 KB Output is correct
57 Correct 1 ms 340 KB Output is correct
58 Correct 2 ms 340 KB Output is correct
59 Correct 1 ms 380 KB Output is correct
60 Correct 1 ms 340 KB Output is correct
61 Correct 1 ms 340 KB Output is correct
62 Correct 1 ms 340 KB Output is correct
63 Correct 1 ms 340 KB Output is correct
64 Correct 1 ms 340 KB Output is correct
65 Correct 1 ms 312 KB Output is correct
66 Runtime error 1 ms 596 KB Execution killed with signal 11
67 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 308 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 308 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 304 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 260 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 0 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 312 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 0 ms 304 KB Output is correct
22 Correct 1 ms 304 KB Output is correct
23 Correct 1 ms 308 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 1 ms 304 KB Output is correct
26 Correct 0 ms 340 KB Output is correct
27 Correct 0 ms 340 KB Output is correct
28 Correct 1 ms 308 KB Output is correct
29 Correct 0 ms 340 KB Output is correct
30 Correct 0 ms 304 KB Output is correct
31 Correct 0 ms 304 KB Output is correct
32 Correct 0 ms 340 KB Output is correct
33 Correct 1 ms 340 KB Output is correct
34 Correct 1 ms 312 KB Output is correct
35 Correct 1 ms 340 KB Output is correct
36 Correct 1 ms 312 KB Output is correct
37 Correct 1 ms 312 KB Output is correct
38 Correct 1 ms 340 KB Output is correct
39 Correct 1 ms 340 KB Output is correct
40 Correct 1 ms 340 KB Output is correct
41 Correct 1 ms 340 KB Output is correct
42 Correct 1 ms 340 KB Output is correct
43 Correct 1 ms 308 KB Output is correct
44 Correct 1 ms 340 KB Output is correct
45 Correct 0 ms 340 KB Output is correct
46 Correct 0 ms 340 KB Output is correct
47 Correct 1 ms 340 KB Output is correct
48 Correct 1 ms 340 KB Output is correct
49 Correct 0 ms 340 KB Output is correct
50 Correct 0 ms 340 KB Output is correct
51 Correct 1 ms 340 KB Output is correct
52 Correct 1 ms 340 KB Output is correct
53 Correct 1 ms 340 KB Output is correct
54 Correct 0 ms 340 KB Output is correct
55 Correct 1 ms 340 KB Output is correct
56 Correct 1 ms 340 KB Output is correct
57 Correct 1 ms 340 KB Output is correct
58 Correct 2 ms 340 KB Output is correct
59 Correct 1 ms 380 KB Output is correct
60 Correct 1 ms 340 KB Output is correct
61 Correct 1 ms 340 KB Output is correct
62 Correct 1 ms 340 KB Output is correct
63 Correct 1 ms 340 KB Output is correct
64 Correct 1 ms 340 KB Output is correct
65 Correct 1 ms 312 KB Output is correct
66 Correct 1 ms 340 KB Output is correct
67 Correct 1 ms 356 KB Output is correct
68 Correct 2 ms 328 KB Output is correct
69 Incorrect 428 ms 384 KB Output isn't correct
70 Halted 0 ms 0 KB -