Submission #982774

#	Time	Username	Problem	Language	Result	Execution time	Memory
982774		Maaxle	Game (APIO22_game)	C++17	0 / 100	0 ms	344 KiB

game

#include "game.h"
#include <bits/stdc++.h>

#define range(it, a, b) for (ll it = a; it < b; it++)
#define all(x) begin(x), end(x)
#define ll long long
#define ull unsigned long long
#define INF64 ((ll) 1 << 62)
#define INF32 (1 << 30)
#define mset multiset
#define uset unordered_set
#define umap unordered_map 
#define pqueue priority_queue 
#define ptr(A) shared_ptr<A>

using namespace std;

vector<vector<int>> adj;
vector<vector<int>> inv_adj;
vector<int> source;
vector<int> destiny;
int K, N;
bool isCycled = 0;

void init(int n, int k) {
  adj.resize(n);
  inv_adj.resize(n);
  destiny.resize(n, INF32);
  source.resize(n, -1);
  k = K;
  n = N;

  range(i, 0, k) {
    if (i < k-1) {
      adj[i].push_back(i+1);
      inv_adj[i+1].push_back(i);
    }
    if (i)
      source[i] = i-1;
    if (i < k-1)
      destiny[i] = i+1;
  }
}

void furthest_source (int i, int& x) {
  if (x <= source[i])
    return;

  source[i] = x;

  if (source[i] >= destiny[i]) {
    isCycled = 1;
    return;
  }

  for (int& it : adj[i]) 
    furthest_source(it, x);
}

void nearest_destiny(int i, int& x) {
  if (x >= destiny[i])
    return;

  destiny[i] = x;

  if (source[i] >= destiny[i]) {
    isCycled = 1;
    return;
  }

  for (int& it : inv_adj[i])
    nearest_destiny(it, x);
}

int add_teleporter(int u, int v) {
  adj[u].push_back(v);
  inv_adj[v].push_back(u);

  if (u == v && u < K) 
    return 1;

  if (u < K)
    furthest_source(v, u);
  furthest_source(v, source[u]);
  if (isCycled)
    return 1;

  if (v < K)
    nearest_destiny(u, v);
  nearest_destiny(u, destiny[v]);
  if (isCycled)
    return 1;
  
  return 0;
}

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