Submission #1058575

#	Time	Username	Problem	Language	Result	Execution time	Memory
1058575		aymanrs	Game (APIO22_game)	C++17	60 / 100	864 ms	5072 KiB

game

#include "game.h"
#include <bits/stdc++.h>
using namespace std;
const int kx = 1000, nx = 30000;
int K;
int reached[nx],reach[nx];
// reached : latest special it can be reached by
// reach : earliest special it can reach
vector<int> g[nx], r[nx];
void init(int n, int k) {
  K=k;
  for(int i = k;i < n;i++) {
    reach[i] = INT_MAX;
    reached[i]=-1;
  }
  for(int i = 0;i < k;i++){
    if(i+1 < k){
      g[i].push_back(i+1);
      r[i+1].push_back(i);
    }
    reached[i]=i;
    reach[i]=i;
  }
}
void spread(int i){
  for(int j : g[i]){
    if(reached[j] < reached[i]){
      reached[j] = reached[i];
      spread(j);
    }
  }
}
void daerps(int i){
  for(int j : r[i]){
    if(reach[j] > reach[i]){
      reach[j]=reach[i];
      daerps(j);
    }
  }
}
int add_teleporter(int u, int v) {
  if(reached[u] >= reach[v]) return 1;
  g[u].push_back(v);
  r[v].push_back(u);
  if(reached[v] < reached[u]){
    reached[v] = reached[u];
    spread(v);
  }
  if(reach[u] > reach[v]){
    reach[u]=reach[v];
    daerps(u);
  }
  return 0;
}

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