Submission #742751

#	Time	Username	Problem	Language	Result	Execution time	Memory
742751		keisuke6	Game (APIO22_game)	C++17	30 / 100	764 ms	262144 KiB

game

#include "game.h"
#include <iostream>
#include <vector>
#include <set>
#include <queue>
#include <map>
using namespace std;
 
vector<map<int,vector<int>>> G(1001);
vector<vector<bool>> P(1001,vector<bool>(30010,false));
int N,K;
void init(int n, int k) {
  N = n;
  K = k;
  for(int i=0;i<k;i++)for(int j=i;j<k;j++) P[i][j] = true;
}
int add_teleporter(int u, int v) {
  for(int i=0;i<K;i++){
    G[i][u].emplace_back(v);
    if(!P[i][u]){
      continue;
    }
    deque<int> q;
    q.push_back(u);
    while(!q.empty()){
      int pos = q.front();
      q.pop_front();
      for(int x:G[i][pos]){
        if(P[i][x]){
          if(x <= i) return 1;
          continue;
        }
        P[i][x] = true;
        q.push_back(x);
      }
      G[i][pos].clear();
    }
  }
  return 0;
}

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