제출 #1291783

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1291783		lucas110550	이주 (IOI25_migrations)	C++20	0 / 100	28 ms	1040 KiB

migrations

#include <vector>
#include <queue>
#include <utility>
#include "migrations.h"

using namespace std;

// Globals (same behavior as Python globals)
static vector<vector<int>> graph_;
static vector<int> depth_;

// Optional: call this if you want to reuse between runs/tests.
void reset_state() {
    graph_.clear();
    depth_.clear();
}

// Builds the graph and depths on the fly.
// Returns 1 if i == N-1, else 0 (same as Python).
int send_message(int N, int i, int Pi) {
    if (graph_.empty()) {
        graph_.assign(N, {});
        depth_.assign(N, 0);
    }

    graph_[Pi].push_back(i);
    graph_[i].push_back(Pi);
    depth_[i] = depth_[Pi] + 1;

    return (i == N - 1) ? 1 : 0;
}

// Finds the two endpoints (u, v) of a longest path (tree diameter).
// Parameter S is unused (kept to match the Python signature).
pair<int,int> longest_path(vector<int> S) {
    const int n = static_cast<int>(graph_.size());
    if (n == 0) return { -1, -1 };

    auto bfs_farthest = [&](int start) -> pair<int, vector<int>> {
        vector<int> dist(n, -1);
        queue<int> q;
        q.push(start);
        dist[start] = 0;
        int far = start;

        while (!q.empty()) {
            int cur = q.front(); q.pop();
            if (dist[cur] > dist[far]) far = cur;
            for (int nei : graph_[cur]) {
                if (dist[nei] == -1) {
                    dist[nei] = dist[cur] + 1;
                    q.push(nei);
                }
            }
        }
        return { far, dist };
    };

    // First BFS from node 0 to get u
    auto [u, dist0] = bfs_farthest(0);
    // Second BFS from u to get v
    auto [v, distu] = bfs_farthest(u);

    return { u, v };
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 30
• Subtask 2: 0 / 70