Submission #980889

#	Time	Username	Problem	Language	Result	Execution time	Memory
980889		nnin	Game (APIO22_game)	C++17	100 / 100	1253 ms	64508 KiB

game

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

int n, k, ret;
int st[300005], en[300005], diff[300005];
vector<int> adj[300005], rev[300005];

void func(int u) {
  if(st[u]>=en[u]) ret = 1;
  if(ret) return;
  int d = __lg(st[u]^en[u]);
  if(d<diff[u]) diff[u] = d;
  else return;
  for(int v:adj[u]) {
    st[v] = max(st[v], st[u]);
    func(v);
  }
  for(int v:rev[u]) {
    en[v] = min(en[v], en[u]);
    func(v);
  }
}

void init(int N, int K) {
  n = N; k = K;
  for(int i=0;i<k;i++) {
    st[i] = i;
    en[i] = i+1;
  }
  for(int i=k;i<n;i++) {
    st[i] = -1;
    en[i] = k;
  }
  for(int i=0;i<n;i++) {
    diff[i] = __lg(st[i]^en[i]);
  }
}

int add_teleporter(int u, int v) {
  adj[u].push_back(v);
  rev[v].push_back(u);
  st[v] = max(st[v], st[u]);
  en[u] = min(en[u], en[v]);
  if(u<k) st[v] = max(st[v], u);
  if(v<k) en[u] = min(en[u], v);
  func(v);
  func(u);
  return ret;
}

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