Submission #1274830

#	Time	Username	Problem	Language	Result	Execution time	Memory
1274830		mehrzad	Migrations (IOI25_migrations)	C++17	0 / 100	2 ms	656 KiB

migrations

#include "migrations.h"
#include <vector>
#include <algorithm>

std::vector<std::vector<int>> adj;
std::vector<int> parent;
int diameter_u, diameter_v, diameter_dist;

std::pair<int, int> bfs_farthest(int start, int n) {
    std::vector<int> dist(n, -1);
    std::vector<int> queue;
    dist[start] = 0;
    queue.push_back(start);
    
    int farthest = start;
    int max_dist = 0;
    
    for (size_t idx = 0; idx < queue.size(); idx++) {
        int u = queue[idx];
        for (int v : adj[u]) {
            if (dist[v] == -1) {
                dist[v] = dist[u] + 1;
                queue.push_back(v);
                if (dist[v] > max_dist) {
                    max_dist = dist[v];
                    farthest = v;
                }
            }
        }
    }
    
    return {farthest, max_dist};
}

int send_message(int N, int i, int Pi) {
    if (i == 1) {
        // Initialize
        adj.clear();
        adj.resize(N);
        parent.clear();
        parent.resize(N);
        parent[0] = -1;
        diameter_u = 0;
        diameter_v = 0;
        diameter_dist = 0;
    }
    
    // Add edge
    adj[i].push_back(Pi);
    adj[Pi].push_back(i);
    parent[i] = Pi;
    
    // Find diameter: BFS from one endpoint, then BFS from farthest point
    auto [far1, dist1] = bfs_farthest(diameter_u, N);
    auto [far2, dist2] = bfs_farthest(far1, N);
    
    int old_u = diameter_u;
    int old_v = diameter_v;
    int old_dist = diameter_dist;
    
    diameter_u = far1;
    diameter_v = far2;
    diameter_dist = dist2;
    
    // Send message only if diameter changed
    if (diameter_dist > old_dist) {
        // Encode both endpoints
        int msg = diameter_u * 10000 + diameter_v;
        return msg;
    }
    
    return 0;
}

std::pair<int, int> longest_path(std::vector<int> S) {
    int last_msg = 0;
    for (int i = 1; i < (int)S.size(); i++) {
        if (S[i] > 0) {
            last_msg = S[i];
        }
    }
    
    if (last_msg == 0) {
        return {0, 0};
    }
    
    int u = last_msg / 10000;
    int v = last_msg % 10000;
    return {u, v};
}

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