제출 #1198669

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1198669		ackhava	Game (APIO22_game)	C++20	60 / 100	4078 ms	38272 KiB

game

#include "game.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define REP(i,o,n) for(auto i=o;i<n;i++)
using namespace std;

int origin[3001000]; // max. origin
int dest[300100]; // min. dest
vector<int> adj[300100];
vector<int> rdj[300100];
int k;

void init(int n, int k) {
  ::k=k;
  REP(i,0,n+10)origin[i]=-1,dest[i]=i;
  REP(i,0,k)origin[i]=i;
  REP(i,0,n+10)adj[i].clear(),rdj[i].clear();
}

void dfs_origin(int node, int v){
  if(origin[node]>=v)return;
  origin[node]=v;
  for(auto i:adj[node])dfs_origin(i,v);
}

void dfs_dest(int node, int v){
  if(dest[node]<=v)return;
  dest[node]=v;
  for(auto i:rdj[node])dfs_dest(i,v);
}

int add_teleporter(int u, int v) {
  if(origin[u]>=dest[v] && origin[u]<=(k-1))return 1;
  adj[u].pb(v);
  rdj[v].pb(u);
  dfs_origin(v,origin[u]);
  dfs_dest(u,dest[v]);
  return 0;
}

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