Submission #594687

#	Time	Username	Problem	Language	Result	Execution time	Memory
594687		Ozy	Game (APIO22_game)	C++17	60 / 100	1262 ms	5028 KiB

game

#include "game.h"
#include <bits/stdc++.h>
using namespace std;
#define lli long long  int
#define rep(i,a,b) for (int i = (a); i <= (b); i++)
#define repa(i,a,b) for (int i = (a); i >= (b); i--)
#define debug(a) cout << #a << " = " << endl
#define debugsl(a) cout << #a << " = " << ", "

#define MAX 30000

lli N,K;
lli des[MAX+2], ori[MAX+2];
    //menor   ,  mayor
vector<lli> hijos[MAX+2];
vector<lli> reves[MAX+2];

void origen(lli pos, lli val) {
    ori[pos] = val;
    for (auto h : hijos[pos]) {
        if (ori[h] < val) origen(h,val);
    }
}

void destino(lli pos, lli val) {
    des[pos] = val;
    for (auto h : reves[pos]) {
        if (des[h] > val) destino(h,val);
    }
}

void init(int n, int k) {
    N = n;
    K = k;

    rep(i,0,k-2) {
        hijos[i].push_back(i+1);
        reves[i+1].push_back(i);
    }
    rep(i,k,n-1) {
        des[i] = N+1;
        ori[i] = -1;
    }
    rep(i,0,k-1) {
        des[i] = i+1;
        ori[i] = i;
    }

}

int add_teleporter(int u, int v) {

    hijos[u].push_back(v);
    reves[v].push_back(u);

    // origen mas grande usando hijos
    if (ori[u] < K && ori[u] > ori[v]) origen(v,ori[u]);

    //destino mas pequeno usando reves

    lli x;
    if (v < K) x = v;
    else x = des[v];

    if (x < des[u]) destino(u,x);

    if (ori[u] >= des[u]) return 1;
    else return false;
}

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