Submission #1224024

#	Time	Username	Problem	Language	Result	Execution time	Memory
1224024		spetr	The Ties That Guide Us (CEOI23_incursion)	C++20	9 / 100	146 ms	7856 KiB

incursion

#include <vector>
#include "incursion.h"
#include <queue>
#include <unordered_set>
using namespace std;

static vector<vector<int>> graf;
static unordered_set<int> vis;

// MARK: compute distances from the safe in assistant’s numbering
vector<int> mark(vector<pair<int,int>> F, int safe) {
    int N = (int)F.size() + 1;
    graf.assign(N+1, {});
    for (auto &e : F) {
        graf[e.first].push_back(e.second);
        graf[e.second].push_back(e.first);
    }
    vector<int> depth(N+1, -1);
    queue<int> q;
    depth[safe] = 0;
    q.push(safe);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : graf[u]) {
            if (depth[v] < 0) {
                depth[v] = depth[u] + 1;
                q.push(v);
            }
        }
    }
    // return depths for rooms 1..N
    return vector<int>(depth.begin()+1, depth.end());
}

// LOCATE: recursively descend to the safe, using only visit() queries
static bool step(int x, int dist) {
    if (dist == 0) 
        return true;  // we are in the safe
    for (int v : graf[x]) {
        if (!vis.count(v)) {
            vis.insert(v);
            int p = visit(v);
            if (p < dist && step(v, p))
                return true;        // found a path
            // wrong branch—go back and try next neighbor
            visit(x);
        }
    }
    return false;
}

void locate(vector<pair<int,int>> F, int curr, int t) {
    int N = (int)F.size() + 1;
    graf.assign(N+1, {});
    for (auto &e : F) {
        graf[e.first].push_back(e.second);
        graf[e.second].push_back(e.first);
    }
    vis.clear();
    vis.insert(curr);
    step(curr, t);
}

• Subtask 0: 0 / 0
• Subtask 1: 9 / 30
• Subtask 2: 0 / 30
• Subtask 3: 0 / 40