Submission #621674

#	Time	Username	Problem	Language	Result	Execution time	Memory
621674		MinaRagy06	Game (APIO22_game)	C++17	2 / 100	15 ms	19104 KiB

game

#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 / 2
• Subtask 2: 0 / 10
• Subtask 3: 0 / 18
• Subtask 4: 0 / 30
• Subtask 5: 0 / 40