Submission #739140

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
739140	2023-05-10T03:41:22 Z	PixelCat	Game (APIO22_game)	C++17	30 / 100	4 ms	464 KB

game

#include "game.h"
#ifdef NYAOWO
#include "grader.cpp"
#endif

#include <bits/stdc++.h>
#define For(i, a, b) for(int i = a; i <= b; i++)
#define Forr(i, a, b) for(int i = a; i >= b; i--)
#define F first
#define S second
#define sz(x) ((int)x.size())
#define all(x) x.begin(), x.end()
#define eb emplace_back
using namespace std;
using LL = long long;
using pii = pair<int, int>;

const int MAXN = 1010;

int n, k, ok;
vector<int> adj[MAXN], rev[MAXN];
int mx[MAXN]; // max special that can reach i
int mn[MAXN]; // min special that i can reach

void init(int _n, int _k) {
    n = _n; k = _k;
    ok = 0;
    For(i, 0, n - 1) {
        adj[i].clear();
        rev[i].clear();
        mx[i] = -1;
        mn[i] = n + 1;
    }
    For(i, 0, k - 2) {
        mx[i + 1] = i;
        mn[i] = i + 1;
        adj[i].eb(i + 1);
        rev[i + 1].eb(i);
    }
}

void dfs_mx(int x, int m) {
    if(mx[x] >= m) return;
    mx[x] = m;
    if(mx[x] >= mn[x]) {
        ok = 1; return;
    }
    for(auto &i:adj[x]) {
        dfs_mx(i, m);
    }
}

void dfs_mn(int x, int m) {
    if(mn[x] <= m) return;
    mn[x] = m;
    if(mx[x] >= mn[x]) {
        ok = 1; return;
    }
    for(auto &i:rev[x]) {
        dfs_mn(i, m);
    }
}

int add_teleporter(int u, int v) {
    if(u < k && v < k) {
        if(u >= v) return 1;
        return 0;
    }
    adj[u].eb(v);
    rev[v].eb(u);
    if(u < k) {
        dfs_mx(v, u);
        dfs_mn(u, mn[v]);
    } else if(v < k) {
        dfs_mx(v, mx[u]);
        dfs_mn(u, v);
    } else {
        dfs_mx(v, mx[u]);
        dfs_mn(u, mn[v]);
    }

    // cout << "mx:";
    // For(i, 0, n - 1) cout << " " << mx[i];
    // cout << "\n";
    // cout << "mn:";
    // For(i, 0, n - 1) cout << " " << mn[i];
    // cout << "\n";

    return ok;
}

/*

4
0
2

*/

Subtask #1
2.0 / 2.0

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

Subtask #2
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	336 KB	Output is correct
2	Correct	0 ms	336 KB	Output is correct
3	Correct	1 ms	336 KB	Output is correct
4	Correct	1 ms	336 KB	Output is correct
5	Correct	1 ms	336 KB	Output is correct
6	Correct	1 ms	336 KB	Output is correct
7	Correct	1 ms	336 KB	Output is correct
8	Correct	0 ms	336 KB	Output is correct
9	Correct	0 ms	336 KB	Output is correct
10	Correct	0 ms	336 KB	Output is correct
11	Correct	1 ms	336 KB	Output is correct
12	Correct	0 ms	356 KB	Output is correct
13	Correct	1 ms	336 KB	Output is correct
14	Correct	1 ms	336 KB	Output is correct
15	Correct	1 ms	356 KB	Output is correct
16	Correct	1 ms	336 KB	Output is correct
17	Correct	1 ms	336 KB	Output is correct
18	Correct	1 ms	336 KB	Output is correct
19	Correct	0 ms	336 KB	Output is correct

Subtask #3
18.0 / 18.0

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

Subtask #4
0.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	336 KB	Output is correct
2	Correct	0 ms	336 KB	Output is correct
3	Correct	1 ms	336 KB	Output is correct
4	Correct	1 ms	336 KB	Output is correct
5	Correct	1 ms	336 KB	Output is correct
6	Correct	1 ms	336 KB	Output is correct
7	Correct	1 ms	336 KB	Output is correct
8	Correct	0 ms	336 KB	Output is correct
9	Correct	0 ms	336 KB	Output is correct
10	Correct	0 ms	336 KB	Output is correct
11	Correct	1 ms	336 KB	Output is correct
12	Correct	0 ms	356 KB	Output is correct
13	Correct	1 ms	336 KB	Output is correct
14	Correct	1 ms	336 KB	Output is correct
15	Correct	1 ms	356 KB	Output is correct
16	Correct	1 ms	336 KB	Output is correct
17	Correct	1 ms	336 KB	Output is correct
18	Correct	1 ms	336 KB	Output is correct
19	Correct	0 ms	336 KB	Output is correct
20	Correct	1 ms	336 KB	Output is correct
21	Correct	1 ms	336 KB	Output is correct
22	Correct	1 ms	336 KB	Output is correct
23	Correct	1 ms	360 KB	Output is correct
24	Correct	4 ms	336 KB	Output is correct
25	Correct	4 ms	424 KB	Output is correct
26	Correct	3 ms	336 KB	Output is correct
27	Correct	2 ms	336 KB	Output is correct
28	Correct	2 ms	336 KB	Output is correct
29	Correct	2 ms	336 KB	Output is correct
30	Runtime error	1 ms	464 KB	Execution killed with signal 11
31	Halted	0 ms	0 KB	-

Subtask #5
0.0 / 40.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	336 KB	Output is correct
2	Correct	0 ms	336 KB	Output is correct
3	Correct	1 ms	336 KB	Output is correct
4	Correct	1 ms	336 KB	Output is correct
5	Correct	1 ms	336 KB	Output is correct
6	Correct	1 ms	336 KB	Output is correct
7	Correct	1 ms	336 KB	Output is correct
8	Correct	0 ms	336 KB	Output is correct
9	Correct	0 ms	336 KB	Output is correct
10	Correct	0 ms	336 KB	Output is correct
11	Correct	1 ms	336 KB	Output is correct
12	Correct	0 ms	356 KB	Output is correct
13	Correct	1 ms	336 KB	Output is correct
14	Correct	1 ms	336 KB	Output is correct
15	Correct	1 ms	356 KB	Output is correct
16	Correct	1 ms	336 KB	Output is correct
17	Correct	1 ms	336 KB	Output is correct
18	Correct	1 ms	336 KB	Output is correct
19	Correct	0 ms	336 KB	Output is correct
20	Correct	1 ms	336 KB	Output is correct
21	Correct	1 ms	336 KB	Output is correct
22	Correct	1 ms	336 KB	Output is correct
23	Correct	1 ms	360 KB	Output is correct
24	Correct	4 ms	336 KB	Output is correct
25	Correct	4 ms	424 KB	Output is correct
26	Correct	3 ms	336 KB	Output is correct
27	Correct	2 ms	336 KB	Output is correct
28	Correct	2 ms	336 KB	Output is correct
29	Correct	2 ms	336 KB	Output is correct
30	Runtime error	1 ms	464 KB	Execution killed with signal 11
31	Halted	0 ms	0 KB	-

Submission #739140

Compilation message

Subtask #1 2.0 / 2.0

Subtask #2 10.0 / 10.0

Subtask #3 18.0 / 18.0

Subtask #4 0.0 / 30.0

Subtask #5 0.0 / 40.0

Subtask #1
2.0 / 2.0

Subtask #2
10.0 / 10.0

Subtask #3
18.0 / 18.0

Subtask #4
0.0 / 30.0

Subtask #5
0.0 / 40.0