Submission #1202219

#	Time	Username	Problem	Language	Result	Execution time	Memory
1202219		dzuizz	Game (APIO22_game)	C++20	60 / 100	4091 ms	35648 KiB

game

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

constexpr int MAXN=3e5+5;
vector<int> g[MAXN],tg[MAXN];
int C[MAXN],G[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);
  }

  memset(C,-1,sizeof C);
  memset(G,0x3f,sizeof G);
  for(int i=0;i<K;++i) C[i]=i,G[i]=i;
}

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

  // upd C
  if(C[v]<C[u]){
    q.emplace(v);
    C[v]=C[u];

    while(q.size()){
      int i=q.front(); q.pop();
      for(auto&j:g[i]) if(C[j]<C[i]){
        q.emplace(j);
        C[j]=C[i];
      }
    }
  }

  // upd G
  if(G[u]>G[v]){
    q.emplace(u);
    G[u]=G[v];
    while(q.size()){
      int i=q.front(); q.pop();
      for(auto&j:tg[i]) if(G[j]>G[i]){
        q.emplace(j);
        G[j]=G[i];
      }
    }
  }

  return G[v] <= C[u];
}

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