Submission #679234

#	Time	Username	Problem	Language	Result	Execution time	Memory
679234		Victor	Game (APIO22_game)	C++17	60 / 100	4090 ms	23916 KiB

game

// #pragma GCC target ("avx,avx2,fma")
// #pragma GCC optimize ("Ofast,inline") // O1 - O2 - O3 - Os - Ofast
// #pragma GCC optimize ("unroll-loops")
#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b) for (int i = (a); i < (b); ++i)
#define per(i, a, b) for (int i = (b)-1; i >= (a); --i)
#define trav(a, x) for (auto &a : x)

#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define pb push_back
#define debug(x) cout << #x << " = " << x << endl

#define umap unordered_map
#define uset unordered_set

typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;

typedef long long ll;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;
typedef vector<pll> vpll;

const int INF = 1'000'000'007;

#include "game.h"

vi graph[300005];
int max_reach[300005];
int N,K;
bool stop=0;

void dfs(int u) {
    //cout<<"u = "<<u<<" max_reach = "<<max_reach[u]<<endl;
    if(max_reach[u]>=u) {
        stop=1;
        return;
    }
    trav(v,graph[u]) if(max_reach[u]>max_reach[v]) {
        max_reach[v]=max_reach[u];
        dfs(v);
    }
}

void init(int n, int k) {
    N=n;
    K=k;
    memset(max_reach,-1,sizeof(max_reach));
}

int add_teleporter(int u, int v) {
    //cout<<"u = "<<u<<" v = "<<v<<endl;
    graph[u].pb(v);
    if(u<K) max_reach[v]=max(max_reach[v],u);
    max_reach[v]=max(max_reach[v],max_reach[u]);
    dfs(v);
    //cout<<endl;
    return stop;
}
/*
#include <cstdio>
#include <cstdlib>
#include <vector>
#include "game.h"

namespace {

int read_int() {
  int x;
  if (scanf("%d", &x) != 1) {
    fprintf(stderr, "Error while reading input\n");
    exit(1);
  }
  return x;
}

}  // namespace

int main() {
  int N = read_int();
  int M = read_int();
  int K = read_int();
  std::vector<int> u(M), v(M);
  for (int i = 0; i < M; ++i) {
    u[i] = read_int();
    v[i] = read_int();
  }

  init(N, K);
  int i;
  for (i = 0; i < M; ++i) {
    int answer = add_teleporter(u[i], v[i]);
    if (answer != 0 && answer != 1) {
      i = -1;
      break;
    } else if (answer == 1) {
      break;
    }
  }
  printf("%d\n", i);
  return 0;
}
*/

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