Submission #912561

#	Time	Username	Problem	Language	Result	Execution time	Memory
912561		efedmrlr	Game (APIO22_game)	C++17	60 / 100	4077 ms	41196 KiB

game

#include "game.h"

// #pragma GCC optimize("O3,Ofast,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>

using namespace std;


#define lli long long int
#define MP make_pair
#define pb push_back
#define REP(i,n) for(int i = 0; (i) < (n); (i)++)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()


void fastio() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}


const double EPS = 0.00001;
const int INF = 1e9+500;
const int ALPH = 26;
const int LGN = 25;
constexpr int MOD = 1e9+7;
int N,K;
vector<vector<int> > adj, adjt;
vector<int> vis;
int timer = 1;
vector<int> arr, arrt;
bool dfs(int node, int val) {
  vis[node] = timer;
  
  if(val <= arr[node]) {
    return 0;
  }
  arr[node] = val;
  if(arr[node] >= arrt[node] && node > K) {
    return 1;
  }
  for(auto c : adj[node]) {
    if(vis[c] == timer) continue;
    if(dfs(c, val)) return 1;
  }
  return 0;
}

bool dfst(int node, int val) {
  vis[node] = timer;
  if(arr[node] >= arrt[node] && node > K) {
    return 1;
  }
  if(val >= arrt[node]) {
    return 0;
  }
  arrt[node] = val;
  if(arr[node] >= arrt[node] && node > K) {
    return 1;
  }
  for(auto c : adjt[node]) {
    if(vis[c] == timer) continue;
    if(dfst(c, val)) return 1;
  }
  return 0;
}


void init(int n, int k) {
  N = n; K = k;
  adj.resize(n + 3, vector<int>());
  adjt.resize(n + 3, vector<int>());
  vis.assign(n + 3, 0);
  arr.assign(n + 3, 0);
  arrt.assign(n + 3, INF);
  for(int i = 1; i<=k; i++) {
    arr[i] = i; arrt[i] = i;
  }

}

int add_teleporter(int u, int v) {
  u++; v++;
  if(u <= K && v <= K) {
    if(u >= v) return 1;
    return 0; 
  }

  if(dfs(v, arr[u])) return 1;
  timer++;
  if(dfst(u, arrt[v])) return 1;
  timer++;
  adj[u].pb(v);
  adjt[v].pb(u);
  return 0;

}

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