Submission #587194

#	Time	Username	Problem	Language	Result	Execution time	Memory
587194		maomao90	Game (APIO22_game)	C++17	100 / 100	1527 ms	107492 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];
int lft[MAXN], rht[MAXN];
bool ans;
 
void init(int N, int K) {
    n = N; k = K;
    n++; k++;
    REP (i, 0, k) {
        lft[i] = i; rht[i] = i + 1;
    }
    REP (i, k, n) {
        lft[i] = 0; rht[i] = k;
    }
}

void propo(int u);

void fix(int u, int v) {
    if (rht[u] <= lft[v]) {
        return;
    }
    if (rht[v] <= lft[u]) {
        ans = 1;
        return;
    }
    if (lft[u] == lft[v] && rht[u] == rht[v]) {
        return;
    }
    int um = lft[u] + rht[u] >> 1, vm = lft[v] + rht[v] >> 1;
    if (um >= rht[v]) {
        rht[u] = um;
        propo(u);
    } else if (vm <= lft[u]) {
        lft[v] = vm;
        propo(v);
    }
}

void propo(int u) {
    for (int v : radj[u]) {
        fix(v, u);
    }
    for (int v : adj[u]) {
        fix(u, v);
    }
}
 
int add_teleporter(int u, int v) {
    u++; v++;
    if (v < k) {
        v--;
    }
    adj[u].pb(v);
    radj[v].pb(u);
    fix(u, v);
    return ans;
}

Compilation message (stderr)

game.cpp: In function 'void fix(int, int)':
game.cpp:63:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   63 |     int um = lft[u] + rht[u] >> 1, vm = lft[v] + rht[v] >> 1;
      |              ~~~~~~~^~~~~~~~
game.cpp:63:48: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   63 |     int um = lft[u] + rht[u] >> 1, vm = lft[v] + rht[v] >> 1;
      |                                         ~~~~~~~^~~~~~~~

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