답안 #983726

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
983726	2024-05-16T02:37:34 Z	gaga999	게임 (APIO22_game)	C++17	30 / 100	4000 ms	3388 KB

game

// #pragma GCC optimize("Ofast,no-stack-protector")
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx,avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
#define lowbit(x) ((x) & -(x))
#define ml(a, b) ((1ll * (a) * (b)) % M)
#define tml(a, b) (a) = ((1ll * (a) * (b)) % M)
#define ad(a, b) ((0ll + (a) + (b)) % M)
#define tad(a, b) (a) = ((0ll + (a) + (b)) % M)
#define mi(a, b) ((0ll + M + (a) - (b)) % M)
#define tmi(a, b) (a) = ((0ll + M + (a) - (b)) % M)
#define tmin(a, b) (a) = min((a), (b))
#define tmax(a, b) (a) = max((a), (b))
#define iter(a) (a).begin(), (a).end()
#define riter(a) (a).rbegin(), (a).rend()
#define inin(a, b) memset((a), (b), sizeof(a))
#define cpy(a, b) memcpy((a), (b), sizeof(a))
#define uni(a) a.resize(unique(iter(a)) - a.begin())
#define size(x) (int)x.size()
#define pb emplace_back
#define mpr make_pair
#define ls(i) ((i) << 1)
#define rs(i) ((i) << 1 | 1)
#define INF 0x3f3f3f3f
#define NIF 0xc0c0c0c0
#define eps 1e-9
#define F first
#define S second
#define AC cin.tie(0)->sync_with_stdio(0)
using namespace std;
typedef long long llt;
typedef unsigned long long ull;
typedef __int128_t lll;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef pair<llt, llt> pll;
typedef pair<llt, int> pli;
typedef complex<double> cd;
// const int M = 998244353;

// random_device rm;
// mt19937 rg(rm());
// default_random_engine rg(rm());
// uniform_int_distribution<int> rd(INT_MIN, INT_MAX);
// uniform_real_distribution<double> rd(0, M_PI);

void db() { cerr << "\n"; }
template <class T, class... U>
void db(T a, U... b) { cerr << a << " ", db(b...); }

inline char gc()
{
    const static int SZ = 1 << 16;
    static char buf[SZ], *p1, *p2;
    if (p1 == p2 && (p2 = buf + fread(p1 = buf, 1, SZ, stdin), p1 == p2))
        return -1;
    return *p1++;
}
void rd() {}
template <typename T, typename... U>
void rd(T &x, U &...y)
{
    x = 0;
    bool f = 0;
    char c = gc();
    while (!isdigit(c))
        f ^= !(c ^ 45), c = gc();
    while (isdigit(c))
        x = (x << 1) + (x << 3) + (c ^ 48), c = gc();
    f && (x = -x), rd(y...);
}

template <typename T>
void prt(T x)
{
    if (x < 0)
        putchar('-'), x = -x;
    if (x > 9)
        prt(x / 10);
    putchar((x % 10) ^ 48);
}

const int N = 3e4 + 5;
int n, k, mx[N], mn[N];
bool ov = 0;
vector<int> e1[N], e2[N];
void init(int _n, int _k)
{
    n = _n, k = _k;
    inin(mn, INF), inin(mx, -1);
    for (int i = 0; i < k; i++)
        mn[i] = mx[i] = i;
}

void dfs2(int u)
{
    if (u < k)
        return;
    if (mx[u] >= mn[u])
        ov = 1;
    for (int v : e2[u])
    {
        if (mn[v] <= mn[u])
            continue;
        mn[v] = mn[u];
        dfs2(v);
    }
}

void dfs1(int u)
{
    if (u < k)
        return;
    if (mx[u] >= mn[u])
        ov = 1;
    for (int v : e1[u])
    {
        if (mx[v] >= mx[u])
            continue;
        mx[v] = mx[u];
        dfs1(v);
    }
}

int add_teleporter(int u, int v)
{
    if (max(u, v) < k)
        return u >= v;
    e1[u].pb(v), e2[v].pb(u);
    tmin(mn[u], mn[v]);
    tmax(mx[v], mx[u]);
    // dfs1(v), dfs2(u);
    for (int i = k; i < n; i++)
        dfs1(i), dfs2(i);
    return ov;
}

// signed main()
// {
//     int n, k, q;
//     rd(n, q, k);
//     init(n, k);
//     for (int i = 0; i < q; i++)
//     {
//         int x, y;
//         rd(x, y);
//         if (add_teleporter(x, y))
//         {
//             // for (int i = 0; i < n; i++)
//             //     db(mx[i], mn[i]);
//             // db(i, x, y);
//             db(i);
//             exit(0);
//         }
//     }
//     db(q);
// }

Subtask #1
2.0 / 2.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	1880 KB	Output is correct
2	Correct	1 ms	1880 KB	Output is correct
3	Correct	1 ms	1880 KB	Output is correct
4	Correct	1 ms	1880 KB	Output is correct
5	Correct	1 ms	1880 KB	Output is correct
6	Correct	1 ms	1880 KB	Output is correct
7	Correct	1 ms	1880 KB	Output is correct

Subtask #2
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	1880 KB	Output is correct
2	Correct	1 ms	1880 KB	Output is correct
3	Correct	1 ms	1880 KB	Output is correct
4	Correct	1 ms	1880 KB	Output is correct
5	Correct	1 ms	1880 KB	Output is correct
6	Correct	1 ms	1880 KB	Output is correct
7	Correct	1 ms	1880 KB	Output is correct
8	Correct	1 ms	1880 KB	Output is correct
9	Correct	1 ms	1880 KB	Output is correct
10	Correct	1 ms	1880 KB	Output is correct
11	Correct	1 ms	1880 KB	Output is correct
12	Correct	1 ms	1880 KB	Output is correct
13	Correct	1 ms	1880 KB	Output is correct
14	Correct	1 ms	1876 KB	Output is correct
15	Correct	1 ms	1880 KB	Output is correct
16	Correct	1 ms	1880 KB	Output is correct
17	Correct	1 ms	1880 KB	Output is correct
18	Correct	1 ms	1880 KB	Output is correct
19	Correct	1 ms	1880 KB	Output is correct

Subtask #3
18.0 / 18.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	1880 KB	Output is correct
2	Correct	1 ms	1880 KB	Output is correct
3	Correct	1 ms	1880 KB	Output is correct
4	Correct	1 ms	1880 KB	Output is correct
5	Correct	1 ms	1880 KB	Output is correct
6	Correct	1 ms	1880 KB	Output is correct
7	Correct	1 ms	1880 KB	Output is correct
8	Correct	1 ms	1880 KB	Output is correct
9	Correct	1 ms	1880 KB	Output is correct
10	Correct	1 ms	1880 KB	Output is correct
11	Correct	1 ms	1880 KB	Output is correct
12	Correct	1 ms	1880 KB	Output is correct
13	Correct	1 ms	1880 KB	Output is correct
14	Correct	1 ms	1876 KB	Output is correct
15	Correct	1 ms	1880 KB	Output is correct
16	Correct	1 ms	1880 KB	Output is correct
17	Correct	1 ms	1880 KB	Output is correct
18	Correct	1 ms	1880 KB	Output is correct
19	Correct	1 ms	1880 KB	Output is correct
20	Correct	9 ms	1880 KB	Output is correct
21	Correct	2 ms	1880 KB	Output is correct
22	Correct	7 ms	2136 KB	Output is correct
23	Correct	9 ms	2136 KB	Output is correct
24	Correct	7 ms	2136 KB	Output is correct
25	Correct	31 ms	2392 KB	Output is correct
26	Correct	49 ms	2136 KB	Output is correct
27	Correct	20 ms	2400 KB	Output is correct
28	Correct	12 ms	1880 KB	Output is correct
29	Correct	16 ms	2136 KB	Output is correct

Subtask #4
0.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	1880 KB	Output is correct
2	Correct	1 ms	1880 KB	Output is correct
3	Correct	1 ms	1880 KB	Output is correct
4	Correct	1 ms	1880 KB	Output is correct
5	Correct	1 ms	1880 KB	Output is correct
6	Correct	1 ms	1880 KB	Output is correct
7	Correct	1 ms	1880 KB	Output is correct
8	Correct	1 ms	1880 KB	Output is correct
9	Correct	1 ms	1880 KB	Output is correct
10	Correct	1 ms	1880 KB	Output is correct
11	Correct	1 ms	1880 KB	Output is correct
12	Correct	1 ms	1880 KB	Output is correct
13	Correct	1 ms	1880 KB	Output is correct
14	Correct	1 ms	1876 KB	Output is correct
15	Correct	1 ms	1880 KB	Output is correct
16	Correct	1 ms	1880 KB	Output is correct
17	Correct	1 ms	1880 KB	Output is correct
18	Correct	1 ms	1880 KB	Output is correct
19	Correct	1 ms	1880 KB	Output is correct
20	Correct	9 ms	1880 KB	Output is correct
21	Correct	2 ms	1880 KB	Output is correct
22	Correct	7 ms	2136 KB	Output is correct
23	Correct	9 ms	2136 KB	Output is correct
24	Correct	7 ms	2136 KB	Output is correct
25	Correct	31 ms	2392 KB	Output is correct
26	Correct	49 ms	2136 KB	Output is correct
27	Correct	20 ms	2400 KB	Output is correct
28	Correct	12 ms	1880 KB	Output is correct
29	Correct	16 ms	2136 KB	Output is correct
30	Execution timed out	4022 ms	3388 KB	Time limit exceeded
31	Halted	0 ms	0 KB	-

Subtask #5
0.0 / 40.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	1880 KB	Output is correct
2	Correct	1 ms	1880 KB	Output is correct
3	Correct	1 ms	1880 KB	Output is correct
4	Correct	1 ms	1880 KB	Output is correct
5	Correct	1 ms	1880 KB	Output is correct
6	Correct	1 ms	1880 KB	Output is correct
7	Correct	1 ms	1880 KB	Output is correct
8	Correct	1 ms	1880 KB	Output is correct
9	Correct	1 ms	1880 KB	Output is correct
10	Correct	1 ms	1880 KB	Output is correct
11	Correct	1 ms	1880 KB	Output is correct
12	Correct	1 ms	1880 KB	Output is correct
13	Correct	1 ms	1880 KB	Output is correct
14	Correct	1 ms	1876 KB	Output is correct
15	Correct	1 ms	1880 KB	Output is correct
16	Correct	1 ms	1880 KB	Output is correct
17	Correct	1 ms	1880 KB	Output is correct
18	Correct	1 ms	1880 KB	Output is correct
19	Correct	1 ms	1880 KB	Output is correct
20	Correct	9 ms	1880 KB	Output is correct
21	Correct	2 ms	1880 KB	Output is correct
22	Correct	7 ms	2136 KB	Output is correct
23	Correct	9 ms	2136 KB	Output is correct
24	Correct	7 ms	2136 KB	Output is correct
25	Correct	31 ms	2392 KB	Output is correct
26	Correct	49 ms	2136 KB	Output is correct
27	Correct	20 ms	2400 KB	Output is correct
28	Correct	12 ms	1880 KB	Output is correct
29	Correct	16 ms	2136 KB	Output is correct
30	Execution timed out	4022 ms	3388 KB	Time limit exceeded
31	Halted	0 ms	0 KB	-

답안 #983726

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