Submission #745160

#	Time	Username	Problem	Language	Result	Execution time	Memory
745160		CyberCraze	Game (APIO22_game)	C++17	0 / 100	1 ms	208 KiB

game

#include <iostream>
#include <vector>
#include <unordered_set>
#include <stack>

using namespace std;

vector<vector<int>> graph;
unordered_set<int> special_planets;
bool has_infinite_stamps;

void init(int n, int k) {
    graph.resize(n);
    special_planets.clear();
    has_infinite_stamps = false;

    for (int i = 0; i < k; i++) {
        special_planets.insert(i);
    }
}

int add_teleporter(int u, int v) {
    graph[u].push_back(v);

    stack<int> stack;
    unordered_set<int> visited;

    stack.push(u);

    while (!stack.empty()) {
        int planet = stack.top();
        stack.pop();

        if (special_planets.count(planet) > 0) {
            has_infinite_stamps = true;
            return 1;
        }

        visited.insert(planet);

        for (int neighbor : graph[planet]) {
            if (visited.count(neighbor) == 0) {
                stack.push(neighbor);
            }
        }
    }

    return 0;
}

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