Submission #1274472

#	Time	Username	Problem	Language	Result	Execution time	Memory
1274472		mehrzad	Migrations (IOI25_migrations)	C++17	0 / 100	30 ms	956 KiB

migrations

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

/* -------------------------------------------------------------
   Global data – survives the whole first run
   ------------------------------------------------------------ */
static int N_global = -1;                 // number of sites, set at first call
static vector<int> parent_vec;            // parent[i] = Pi
static int answer_u = -1, answer_v = -1;  // diameter ends
static const string FILE_NAME = "answer.txt";

/* -------------------------------------------------------------
   Helper: find farthest vertex and distances (BFS)
   ------------------------------------------------------------ */
static pair<int, vector<int>> bfs_farthest(int start,
                                            const vector<vector<int>>& adj)
{
    int n = (int)adj.size();
    vector<int> dist(n, -1);
    queue<int> q;
    dist[start] = 0;
    q.push(start);
    int far = start;

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

/* -------------------------------------------------------------
   The function called while the team visits the sites
   ------------------------------------------------------------ */
int send_message(int N, int i, int Pi)
{
    // first call – initialise structures
    if (N_global == -1) {
        N_global = N;
        parent_vec.assign(N, -1);   // parent[0] stays -1
    }

    // store the parent of site i
    parent_vec[i] = Pi;

    // after the last site we know the whole tree
    if (i == N - 1) {
        // build adjacency list
        vector<vector<int>> adj(N);
        for (int v = 1; v < N; ++v) {
            int p = parent_vec[v];
            adj[v].push_back(p);
            adj[p].push_back(v);
        }

        // two BFS to obtain a diameter
        auto first = bfs_farthest(0, adj);
        int a = first.first;
        auto second = bfs_farthest(a, adj);
        int b = second.first;

        answer_u = a;
        answer_v = b;

        // write the answer to a temporary file for the second run
        ofstream ofs(FILE_NAME, ios::out | ios::trunc);
        if (ofs) {
            ofs << answer_u << ' ' << answer_v << '\n';
            ofs.close();
        }
    }

    // we do not need to send any message
    return 0;   // S[i] = 0  → no message
}

/* -------------------------------------------------------------
   The function called after all messages have been collected
   ------------------------------------------------------------ */
pair<int,int> longest_path(vector<int> S)
{
    // read the answer from the file written after the last call
    ifstream ifs(FILE_NAME);
    int u = 0, v = 0;
    if (ifs) {
        ifs >> u >> v;
        ifs.close();
        return {u, v};
    }
    // fallback – should never happen in correct runs
    return {0, 0};
}

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