Submission #730468

#	Time	Username	Problem	Language	Result	Execution time	Memory
730468		vjudge1	Game (APIO22_game)	C++17	100 / 100	1059 ms	64028 KiB

game

#include <bits/stdc++.h>
using namespace std;
#include "game.h"

int N, K;
int l[300000], r[300000];  // max_to, min_from
vector<int> adj[300000], radj[300000];
int last[300000];
int res = 0;

void init(int n, int k) {
        N = n, K = k;
        for (int i = 0; i < K; i++) l[i] = i, r[i] = i + 1;
        for (int i = K; i < N; i++) l[i] = 0, r[i] = K + 1;
        for (int i = 0; i < N; i++) last[i] = __lg(l[i] ^ r[i]);
}

void update(int u) {
        if (res == 1) return;
        if (r[u] <= l[u]) return void(res = 1);
        int cur = __lg(l[u] ^ r[u]);
        if (cur == last[u]) return;
        last[u] = cur;
        for (int v : adj[u]) {
                if (l[v] < l[u]) l[v] = l[u], update(v);
        }
        for (int v : radj[u]) {
                if (r[v] > r[u]) r[v] = r[u], update(v);
        }
}

int add_teleporter(int u, int v) {
        if (v <= u && u < K) return 1;
        if (u == v) return 0;

        adj[u].emplace_back(v);
        radj[v].emplace_back(u);

        int val = u < K ? max(u + 1, l[u]) : l[u];

        if (l[v] < val) l[v] = val, update(v);
        if (r[u] > r[v]) r[u] = r[v], update(u);

        return res;
}

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