Submission #1202209

#	Time	Username	Problem	Language	Result	Execution time	Memory
1202209		dzuizz	Game (APIO22_game)	C++20	30 / 100	4059 ms	7292 KiB

game

// Subtask 1
#include "game.h"
#include <bits/stdc++.h>
using namespace std;

constexpr int MAXN=1e5+5;
vector<int> g[MAXN],tg[MAXN];
queue<int> q;
bool vi[MAXN];
int N,K;

void init(int n, int k) {
  N=n,K=k;

  for(int i=0;i<K-1;++i){
    g[i].emplace_back(i+1);
    tg[i+1].emplace_back(i);
  }
}

int add_teleporter(int u, int v) {
  g[u].emplace_back(v);
  tg[v].emplace_back(u);

  int mini=INT_MAX,maxi=-1;

  // find min goto
  memset(vi,0,sizeof vi);
  q.emplace(v); vi[v]=1;
  while(q.size()){
    int i=q.front(); q.pop();
    if(i<K) mini=min(mini,i);
    for(auto&j:g[i]) if(!vi[j]){
      q.emplace(j); vi[j]=1;
    }
  }

  // find max comefrom
  memset(vi,0,sizeof vi);
  q.emplace(u); vi[u]=1;
  while(q.size()){
    int i=q.front(); q.pop();
    if(i<K) maxi=max(maxi,i);
    for(auto&j:tg[i]) if(!vi[j]){
      q.emplace(j); vi[j]=1;
    }
  }

  //cerr<<mini<<" "<<maxi<<'\n';
  return mini <= maxi;
}

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