oj.uz

Submission #621674

# Submission time Handle Problem Language Result Execution time Memory
621674 2022-08-04T01:46:03 Z MinaRagy06 Game (APIO22_game) C++17
2 / 100
 15 ms 19104 KB 
#include <bits/stdc++.h>
#include "game.h"
// #include "grader.cpp"
using namespace std;
#define lesgooo ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define endl	'\n'

vector<int> adj[int(3e5+5)], adjj[int(3e5+5)], vis(3e5+5, 0), inStack(3e5+5, 0), go(3e5+5, 0), rec(3e5+5, 0);
int n, k, stamp, v, u, ctr, cycle;
void init(int nn, int kk)
{
    n = nn, k = kk;
    for (int i = 0; i < n; i++) adj[i].clear();
    for (int i = 0; i < n; i++) go[i] = 1e9, rec[i] = -1e9;
}
int dfs(int i, int x)
{
    if (vis[i] == ctr) return 0;
    if (rec[i] >= x) return rec[i]>=go[i];
    vis[i] = ctr, rec[i] = x;
    int ans = (rec[i]>=go[i]);
    for (auto nxt : adj[i]) ans = max(ans, dfs(nxt, x));
    return ans;
}
int rev(int i, int x)
{
    if (vis[i] == ctr) return 0;
    if (go[i] <= x) return rec[i]>=go[i];
    vis[i] = ctr, go[i] = x;
    int ans = (rec[i]>=go[i]);
    for (auto nxt : adjj[i]) ans = max(ans, rev(nxt, x));
    return ans;
}
int add_teleporter(int uu, int vv)
{
    u = uu, v = vv;
    int ans = 0;
    if (u < k && v < k) return u >= v;
    if (u < k)
    {
        if (u > 0) return dfs(v, u);
        else return 0;
    }
    if (v < k)
    {
        if (v < k-1) return rev(u, v);
        else return 0;
    }
    if (rec[u]>=go[v]) return 1;
    adj[u].push_back(v);
    adjj[v].push_back(u);
    if (go[v]) ans = max(ans, rev(u, go[v]));
    if (rec[u]) ans = max(ans, dfs(v, rec[u]));
    ctr++;
    return ans;
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 19044 KB Output is correct
2 Correct 13 ms 18976 KB Output is correct
3 Correct 14 ms 19100 KB Output is correct
4 Correct 12 ms 19024 KB Output is correct
5 Correct 12 ms 18968 KB Output is correct
6 Correct 11 ms 19104 KB Output is correct
7 Correct 13 ms 19040 KB Output is correct

Subtask #2
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 19044 KB Output is correct
2 Correct 13 ms 18976 KB Output is correct
3 Correct 14 ms 19100 KB Output is correct
4 Correct 12 ms 19024 KB Output is correct
5 Correct 12 ms 18968 KB Output is correct
6 Correct 11 ms 19104 KB Output is correct
7 Correct 13 ms 19040 KB Output is correct
8 Correct 15 ms 19024 KB Output is correct
9 Correct 11 ms 19020 KB Output is correct
10 Incorrect 13 ms 19004 KB Wrong Answer[1]
11 Halted 0 ms 0 KB -

Subtask #3
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 19044 KB Output is correct
2 Correct 13 ms 18976 KB Output is correct
3 Correct 14 ms 19100 KB Output is correct
4 Correct 12 ms 19024 KB Output is correct
5 Correct 12 ms 18968 KB Output is correct
6 Correct 11 ms 19104 KB Output is correct
7 Correct 13 ms 19040 KB Output is correct
8 Correct 15 ms 19024 KB Output is correct
9 Correct 11 ms 19020 KB Output is correct
10 Incorrect 13 ms 19004 KB Wrong Answer[1]
11 Halted 0 ms 0 KB -

Subtask #4
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 19044 KB Output is correct
2 Correct 13 ms 18976 KB Output is correct
3 Correct 14 ms 19100 KB Output is correct
4 Correct 12 ms 19024 KB Output is correct
5 Correct 12 ms 18968 KB Output is correct
6 Correct 11 ms 19104 KB Output is correct
7 Correct 13 ms 19040 KB Output is correct
8 Correct 15 ms 19024 KB Output is correct
9 Correct 11 ms 19020 KB Output is correct
10 Incorrect 13 ms 19004 KB Wrong Answer[1]
11 Halted 0 ms 0 KB -

Subtask #5
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 19044 KB Output is correct
2 Correct 13 ms 18976 KB Output is correct
3 Correct 14 ms 19100 KB Output is correct
4 Correct 12 ms 19024 KB Output is correct
5 Correct 12 ms 18968 KB Output is correct
6 Correct 11 ms 19104 KB Output is correct
7 Correct 13 ms 19040 KB Output is correct
8 Correct 15 ms 19024 KB Output is correct
9 Correct 11 ms 19020 KB Output is correct
10 Incorrect 13 ms 19004 KB Wrong Answer[1]
11 Halted 0 ms 0 KB -