oj.uz

Submission #586998

# Submission time Handle Problem Language Result Execution time Memory
586998 2022-07-01T07:56:51 Z maomao90 Game (APIO22_game) C++17
2 / 100
 10 ms 14436 KB 
#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 (vis[v]) continue;
        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];
            vis[v] = 1;
            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 (vis[v]) continue;
        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];
            vis[v] = 1;
            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];
            vis[v] = 1;
            dfs(v);
        }
        for (int i : stk) {
            vis[i] = 0;
        }
        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];
            vis[v] = 1;
            rdfs(u);
        }
        for (int i : rstk) {
            vis[i] = 0;
        }
        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 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};
            }
        }
        for (int i : tstk) {
            vis[i] = 0;
        }
        tstk.clear();
        REP (i, 0, SZ(rstk)) {
            tstk.pb(rstk[i]);
        }
        RREP (i, SZ(stk) - 1, 0) {
            tstk.pb(stk[i]);
        }
        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};
            }
        }
        for (int i : tstk) {
            vis[i] = 0;
        }
    }
    return ans;
}

Compilation message

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:153:56: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  153 |             int lo = mn[u].FI, hi = mn[u].SE, mid = lo + hi >> 1;
      |                                                     ~~~^~~~
game.cpp:179:56: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  179 |             int lo = mx[u].FI, hi = mx[u].SE, mid = lo + hi >> 1;
      |                                                     ~~~^~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14288 KB Output is correct
2 Correct 7 ms 14416 KB Output is correct
3 Correct 7 ms 14416 KB Output is correct
4 Correct 7 ms 14292 KB Output is correct
5 Correct 8 ms 14300 KB Output is correct
6 Correct 7 ms 14416 KB Output is correct
7 Correct 9 ms 14288 KB Output is correct

Subtask #2
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14288 KB Output is correct
2 Correct 7 ms 14416 KB Output is correct
3 Correct 7 ms 14416 KB Output is correct
4 Correct 7 ms 14292 KB Output is correct
5 Correct 8 ms 14300 KB Output is correct
6 Correct 7 ms 14416 KB Output is correct
7 Correct 9 ms 14288 KB Output is correct
8 Correct 8 ms 14288 KB Output is correct
9 Correct 10 ms 14288 KB Output is correct
10 Correct 7 ms 14288 KB Output is correct
11 Correct 9 ms 14436 KB Output is correct
12 Correct 8 ms 14320 KB Output is correct
13 Incorrect 8 ms 14416 KB Wrong Answer[1]
14 Halted 0 ms 0 KB -

Subtask #3
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14288 KB Output is correct
2 Correct 7 ms 14416 KB Output is correct
3 Correct 7 ms 14416 KB Output is correct
4 Correct 7 ms 14292 KB Output is correct
5 Correct 8 ms 14300 KB Output is correct
6 Correct 7 ms 14416 KB Output is correct
7 Correct 9 ms 14288 KB Output is correct
8 Correct 8 ms 14288 KB Output is correct
9 Correct 10 ms 14288 KB Output is correct
10 Correct 7 ms 14288 KB Output is correct
11 Correct 9 ms 14436 KB Output is correct
12 Correct 8 ms 14320 KB Output is correct
13 Incorrect 8 ms 14416 KB Wrong Answer[1]
14 Halted 0 ms 0 KB -

Subtask #4
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14288 KB Output is correct
2 Correct 7 ms 14416 KB Output is correct
3 Correct 7 ms 14416 KB Output is correct
4 Correct 7 ms 14292 KB Output is correct
5 Correct 8 ms 14300 KB Output is correct
6 Correct 7 ms 14416 KB Output is correct
7 Correct 9 ms 14288 KB Output is correct
8 Correct 8 ms 14288 KB Output is correct
9 Correct 10 ms 14288 KB Output is correct
10 Correct 7 ms 14288 KB Output is correct
11 Correct 9 ms 14436 KB Output is correct
12 Correct 8 ms 14320 KB Output is correct
13 Incorrect 8 ms 14416 KB Wrong Answer[1]
14 Halted 0 ms 0 KB -

Subtask #5
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14288 KB Output is correct
2 Correct 7 ms 14416 KB Output is correct
3 Correct 7 ms 14416 KB Output is correct
4 Correct 7 ms 14292 KB Output is correct
5 Correct 8 ms 14300 KB Output is correct
6 Correct 7 ms 14416 KB Output is correct
7 Correct 9 ms 14288 KB Output is correct
8 Correct 8 ms 14288 KB Output is correct
9 Correct 10 ms 14288 KB Output is correct
10 Correct 7 ms 14288 KB Output is correct
11 Correct 9 ms 14436 KB Output is correct
12 Correct 8 ms 14320 KB Output is correct
13 Incorrect 8 ms 14416 KB Wrong Answer[1]
14 Halted 0 ms 0 KB -