Submission #586955

#	Time	Username	Problem	Language	Result	Execution time	Memory
586955		maomao90	Game (APIO22_game)	C++17	2 / 100	136 ms	262144 KiB

game

#include <bits/stdc++.h>
#include "game.h"
using namespace std;
 
#define REP(i, j, k) for (int i = (j); i < (k); i++)
#define RREP(i, j, k) for (int i = (j); i >= (k); i--)
 
template <class T>
inline bool mnto(T &a, const T b) {return a > b ? a = b, 1 : 0;}
template <class T>
inline bool mxto(T &a, const T b) {return a < b ? a = b, 1 : 0;}
 
typedef long long ll;
#define FI first
#define SE second
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
#define ALL(x) x.begin(), x.end()
#define SZ(x) (int) x.size()
#define pb push_back
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<ll> vll;
typedef tuple<int, int, int> iii;
 
#ifndef DEBUG
#define cerr if (0) cerr
#endif
 
const int MAXN = 300005;
const int INF = 1000000005;
const ll LINF = 1000000000000000005;
 
int n, k;
vi adj[MAXN], radj[MAXN];
ii mn[MAXN], mx[MAXN];
vi stk, rstk;
int vis[MAXN];
bool ans;
 
void init(int N, int K) {
    n = N; k = K;
    REP (i, 0, k) {
        mn[i] = mx[i] = {i, i};
    }
    int lo = -1, hi = k, mid = lo + hi >> 1;
    REP (i, k, n) {
        mn[i] = {mid + 1, hi}; mx[i] = {lo, mid};
    }
}
 
void dfs(int u) {
    if (u < k) {
        return;
    }
    if (mn[u].SE <= mx[u].FI) {
        ans = 1;
        return;
    }
    for (int v : adj[u]) {
        if (mx[u].FI > mx[v].SE || mn[v] == mx[v]) {
            if (mn[v].SE <= mx[u].FI) {
                ans = 1;
                return;
            }
            mx[v] = mn[v];
            dfs(v);
        }
    }
    stk.pb(u);
}
 
void rdfs(int u) {
    if (u < k) {
        return;
    }
    if (mn[u].SE <= mx[u].FI) {
        ans = 1;
        return;
    }
    for (int v : radj[u]) {
        if (mn[u].SE < mn[v].FI || mn[v] == mx[v]) {
            if (mn[u].SE <= mx[v].FI) {
                ans = 1;
                return;
            }
            mn[v] = mx[v];
            rdfs(v);
        }
    }
    rstk.pb(u);
}
 
int add_teleporter(int u, int v) {
    if (u < k && v < k) {
        if (v <= u) {
            return 1;
        } else {
            return 0;
        }
    }
    adj[u].pb(v);
    radj[v].pb(u);
    while (1) {
        stk.clear();
        rstk.clear();
        if (mx[u].FI > mx[v].SE || mn[v] == mx[v]) {
            if (mn[v].SE <= mx[u].FI) {
                ans = 1;
                break;
            }
            mx[v] = mn[v];
            dfs(v);
        }
        if (mn[v].SE < mn[u].FI || mn[u] == mx[u]) {
            if (mn[v].SE <= mx[u].FI) {
                ans = 1;
                break;
            }
            mn[u] = mx[u];
            rdfs(u);
        }
        if (ans) {
            break;
        }
        if (stk.empty() && rstk.empty()) {
            break;
        }
        vi tstk;
        REP (i, 0, SZ(stk)) {
            tstk.pb(stk[i]);
        }
        RREP (i, SZ(rstk) - 1, 0) {
            tstk.pb(rstk[i]);
        }
        for (int i : tstk) {
            vis[i] = 0;
        }
        for (int u : tstk) {
            if (vis[u]) {
                continue;
            }
            vis[u] = 1;
            int lo = mn[u].FI, hi = mn[u].SE, mid = lo + hi >> 1;
            for (int v : adj[u]) {
                if (lo <= mn[v].FI && mn[v].SE <= mid) {
                    mn[u] = {lo, mid};
                    break;
                }
            }
            if (mn[u].SE != mid) {
                mn[u] = {mid + 1, hi};
            }
        }
        tstk.clear();
        REP (i, 0, SZ(rstk)) {
            tstk.pb(rstk[i]);
        }
        RREP (i, SZ(stk) - 1, 0) {
            tstk.pb(stk[i]);
        }
        for (int i : tstk) {
            vis[i] = 0;
        }
        for (int u : tstk) {
            if (vis[u]) {
                continue;
            }
            vis[u] = 1;
            int lo = mx[u].FI, hi = mx[u].SE, mid = lo + hi >> 1;
            for (int v : radj[u]) {
                if (mid + 1 <= mx[v].FI && mx[v].SE <= hi) {
                    mx[u] = {mid + 1, hi};
                    break;
                }
            }
            if (mx[u].FI != mid + 1) {
                mx[u] = {lo, mid};
            }
        }
    }
    return ans;
}

Compilation message (stderr)

game.cpp: In function 'void init(int, int)':
game.cpp:46:35: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   46 |     int lo = -1, hi = k, mid = lo + hi >> 1;
      |                                ~~~^~~~
game.cpp: In function 'int add_teleporter(int, int)':
game.cpp:144:56: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  144 |             int lo = mn[u].FI, hi = mn[u].SE, mid = lo + hi >> 1;
      |                                                     ~~~^~~~
game.cpp:170:56: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  170 |             int lo = mx[u].FI, hi = mx[u].SE, mid = lo + hi >> 1;
      |                                                     ~~~^~~~

• Subtask 1: 2 / 2
• Subtask 2: 0 / 10
• Subtask 3: 0 / 18
• Subtask 4: 0 / 30
• Subtask 5: 0 / 40