Submission #1269322

#	Time	Username	Problem	Language	Result	Execution time	Memory
1269322		sula2	Migrations (IOI25_migrations)	C++20	20 / 100	31 ms	1216 KiB

migrations

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

vector<int> adj[10000];
int X = 0, Y = 0;

pair<int,int> dfs(int u, int p = -1) {
    pair<int,int> res = {0, u};
    for (int v : adj[u]) {
        if (v == p) continue;
        auto z = dfs(v, u);
        z.first++;
        res = max(res, z);
    }
    return res;
}

int send_message(int N, int i, int Pi) {
    adj[i].push_back(Pi);
    adj[Pi].push_back(i);
    int nX = 0, nY = 0;
    if (i >= N-3) {
        nX = dfs(0).second;
        nY = dfs(nX).second;
        if (nX == Y) swap(nX, nY);
        X = nX, Y = nY;
    }
    int res = 0;
    if (i == N-2) res = nX;
    else if (i == N-1) res = i == nX ? nY + N : nY;
    return res;
}

pair<int,int> longest_path(vector<int> S) {
    int n = S.size();
    int u = S[n-2];
    int v = S[n-1];
    if (v >= n) {
        u = v - n;
        v = n-1;
    }
    return {u, v};
}

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