Submission #1207942

#	Time	Username	Problem	Language	Result	Execution time	Memory
1207942		al95ireyiz	Game (APIO22_game)	C++20	0 / 100	191 ms	327680 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;
  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;
  }
}

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: 0 / 2
• Subtask 2: 0 / 10
• Subtask 3: 0 / 18
• Subtask 4: 0 / 30
• Subtask 5: 0 / 40