Submission #821568

#	Time	Username	Problem	Language	Result	Execution time	Memory
821568		radaiosm7	Game (APIO22_game)	C++17	30 / 100	4017 ms	3708 KiB

game

#include "game.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> adj[30005];
int visited[30005];
int ind[30005];
int i, n, k, s;
int seg[120020];

int Query(int from, int to, int start=0, int ende=30005, int indx=1) {
  if (from == start && to == ende) return seg[indx];
  int mid = (start+ende)/2;
  if (to <= mid) return Query(from, to, start, mid, 2*indx);
  if (from > mid) return Query(from, to, mid+1, ende, 2*indx+1);
  else return min(Query(from, mid, start, mid, 2*indx), Query(mid+1, to, mid+1, ende, 2*indx+1));
}

void Insert(int val, int start=0, int ende=30005, int indx=1) {
  if (start == ende) {
    seg[indx] = val;
    ind[val] = s;
    ++s;
    return;
  }

  int mid = (start+ende)/2;
  if (s <= mid) Insert(val, start, mid, 2*indx);
  else Insert(val, mid+1, ende, 2*indx+1);
  seg[indx] = min(seg[2*indx], seg[2*indx+1]);
}

void Erase(int start=0, int ende=30005, int indx=1) {
  if (start == ende) {
    ind[seg[indx]] = -2;
    seg[indx] = INT_MAX;
    --s;
    return;
  }

  int mid = (start+ende)/2;
  if (s-1 <= mid) Erase(start, mid, 2*indx);
  else Erase(mid+1, ende, 2*indx+1);
  seg[indx] = min(seg[2*indx], seg[2*indx+1]);
}

void build(int start=0, int ende=30005, int indx=1) {
  if (start == ende) {
    seg[indx] = INT_MAX;
    return;
  }

  int mid = (start+ende)/2;
  build(start, mid, 2*indx);
  build(mid+1, ende, 2*indx+1);
  seg[indx] = min(seg[2*indx], seg[2*indx+1]);
}

void init(int N, int K) {
  n = N;
  k = K;
  for (i=0; i < k-1; ++i) adj[i].push_back(i+1);
  build();
}

bool dfs(int x) {
  Insert(x);
  bool ok = false;

  for (auto y : adj[x]) {
    if (ind[y] == -2) continue;
    else if (ind[y] == -1) ok |= dfs(y);
    else if (Query(ind[y], ind[x]) < k) return true;
    if (ok) break;
  }

  Erase();
  return ok;
}

int add_teleporter(int u, int v) {
  fill(ind, ind+n, -1);
  if (u == v) return (u < k) ? 1 : 0;
  adj[u].push_back(v);
  s = 0;
  Insert(u);
  if (dfs(v)) return 1;
  else Erase();
  return 0;
}

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