Submission #1225104

#	Time	Username	Problem	Language	Result	Execution time	Memory
1225104		SpyrosAliv	Game (APIO22_game)	C++20	0 / 100	0 ms	408 KiB

game

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

// for each node store the latest special node it can be reached from (from[u])
// and the earliest special node it can reach (to[u])
// when connecting u and v such that to[v] <= from[u] answer is 1

vector<vector<int>> g, rev;
int n, k;
vector<int> from, to;

void init(int N, int K) {
    n = N;
    k = K;
    g.clear();
    rev.clear();
    from.clear();
    to.clear();
    g.resize(n+1);
    rev.resize(n+1);
    from.assign(n+1, -1);
    to.resize(n+1, n+1);
    for (int i = 1; i <= k; i++) {
        from[i] = i;
        to[i] = i;
    }
    for (int i = 1; i < k; i++) {
        g[i].push_back(i+1);
        rev[i+1].push_back(i);
    }
}

void set_to(int u, int val) {
    if (to[u] <= val) return;
    to[u] = val;
    for (auto next: rev[u]) {
        set_to(next, val);
    }
}

void set_from(int u, int val) {
    if (from[u] >= val) return;
    from[u] = val;
    for (auto next: g[u]) {
        set_from(next, val);
    }
}

int add_teleporter(int u, int v) {
    u++;
    v++;
    if (to[v] <= from[u]) return 1;
    if (u == v && u <= k) return 1;
    if (u == v) return 0;
    g[u].push_back(v);
    rev[v].push_back(u);
    set_to(u, to[v]);
    set_from(v, from[u]);
    //for (int i = 1; i <= n; i++) {
    //  cout << "DEB: " << to[i] << " " << from[i] << "\n";
    //}
    //cout << "\n";
    return 0;
}

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