oj.uz

Submission #982774

# Submission time Handle Problem Language Result Execution time Memory
982774 2024-05-14T17:47:12 Z Maaxle Game (APIO22_game) C++17
0 / 100
 0 ms 344 KB 
#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.0 / 2.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Wrong Answer[1]
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Wrong Answer[1]
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Wrong Answer[1]
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Wrong Answer[1]
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Wrong Answer[1]
2 Halted 0 ms 0 KB -