Submission #1136061

#	Time	Username	Problem	Language	Result	Execution time	Memory
1136061		Ludissey	Game (APIO22_game)	C++20	0 / 100	0 ms	412 KiB

game

#include "game.h"

#include <bits/stdc++.h>
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
 
using namespace std;

vector<vector<int>> edge;
vector<vector<int>> invedge;
vector<int> r; 
vector<int> s; 
int n,k;

void init(int _n, int _k) {
  n=_n;
  k=_k;
  edge.resize(n);
  invedge.resize(n);
  r.resize(n,-1);
  s.resize(n,1e9);
  for (int i = 0; i < k-1; i++)
  {
    edge[i].push_back(i+1);
    invedge[i+1].push_back(i);
    r[i]=s[i]=i;
    r[i+1]=s[i+1]=i+1;
  }

}


bool rdfs(int x, int v){
  if(v>=s[x]) return true;
  if(r[x]>=v) return false;
  r[x]=v;
  for (auto u : edge[x]) 
    if(rdfs(u,v)) return true;
  return false;

}

bool sdfs(int x, int v){
  if(r[x]>=v) return true;
  if(s[x]<=v) return false;
  s[x]=v;
  for (auto u : invedge[x]) 
    if(sdfs(u,v)) return true;
  return false;
}

int add_teleporter(int u, int v) {
  bool b=false;
  edge[u].push_back(v);
  invedge[v].push_back(u);
  if(rdfs(v,r[u])) b=true;
  if(sdfs(u,s[v])) b=true;
  return (int)b;
}

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