Submission #1135495

#	Time	Username	Problem	Language	Result	Execution time	Memory
1135495		Ludissey	Game (APIO22_game)	C++20	0 / 100	0 ms	408 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<bool> r; 
vector<bool> s; 
int n,k;

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


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

}

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

int add_teleporter(int u, int v) {
  bool b=false;
  if(u<k&&v<k){
    if(u<v) return 0;
    return 1;
  }
  edge[u].push_back(v);
  invedge[v].push_back(u);
  if((r[u]||u<k)&&rdfs(v)) b=true;
  if((s[v]||v<k)&&sdfs(u)) 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