Submission #1255062

#	Time	Username	Problem	Language	Result	Execution time	Memory
1255062		vpinx	Migrations (IOI25_migrations)	C++20	10 / 100	30 ms	1032 KiB

migrations

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

vector<vector<int>> adj;

int send_message(int n, int i, int pi) {
    if (i == 1) adj.resize(n);
    adj[i].push_back(pi);
    adj[pi].push_back(i);
    if (i < n - 1) return 0;
    
    vector<bool> vis(n, false);
    vis[0] = true;
    
    stack<pair<int, int>> s;
    s.push({0, 0});
    
    int message, ans = -1;
    while (!s.empty()) {
        auto [at, d] = s.top();
        s.pop();
        
        if (d > ans) ans = d, message = at;
        for (int to : adj[at]) {
            if (!vis[to]) {
                vis[to] = true;
                s.push({to, d + 1});
            }
        }
    }
    return message;
}

pair<int, int> longest_path(vector<int> s) {
    return {0, s[s.size() - 1]};
}

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