제출 #1006041

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1006041		amirhoseinfar1385	게임 (APIO22_game)	C++17	12 / 100	4 ms	14936 KiB

game

#include "game.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn=300000+10;
int n,k,l[maxn],r[maxn];
vector<int>adj[maxn],revadj[maxn];

void init(int n_, int k_) {
  n=n_;
  k=k_;
  for(int i=0;i<=k;i++){
    l[i]=i;
    r[i]=i+1;
  }
  for(int i=k+1;i<=n;i++){
    l[i]=-1;
    r[i]=k+1;
  }
  for(int i=0;i<=n;i++){
    adj[i].clear();
    revadj[i].clear();
  }
}

int calc(int u,int v){
  if(u==v){
    return 1;
  }
  if(r[u]<=l[v]){
    return 0;
  }
 // cout<<u<<" "<<v<<endl;
  if(l[u]>=r[v]){
    return 1;
  }
  if(l[u]<=l[v]&&r[v]>=r[u]){
    return 0;
  }
  if(r[v]<=(l[u]+r[u])/2){
    r[u]=(l[u]+r[u])/2;
    for(auto x:revadj[u]){
      if(calc(x,u)){
        return 1;
      }
    }
    for(auto x:adj[u]){
      if(calc(u,x)){
        return 1;
      }
    }
  }
  if(l[u]>=(l[v]+r[v])/2){
    l[v]=(l[v]+r[v])/2;
    for(auto x:adj[v]){
        if(calc(v,x)){
          return 1;
        }
    }
    for(auto x:revadj[v]){
      if(calc(x,v)){
        return 1;
      }
    }
  }
  return 0;
}

int add_teleporter(int u, int v) {
  u++;
  if(v>=k){
    v++;
  }
  adj[u].push_back(v);
  revadj[v].push_back(u);
  if(calc(u,v)){
 //   cout<<"1hey"<<endl;
    return 1;
  }
  //cout<<"0hey"<<endl;
  return 0;
}

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