Submission #1251634

#	Time	Username	Problem	Language	Result	Execution time	Memory
1251634		yeyso2	Migrations (IOI25_migrations)	C++20	0 / 100	0 ms	408 KiB

migrations

#include "migrations.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> p;
void dfs(int u, vector<vector<int>> &adj, vector<int> &dist)
{
    for (int v : adj[u])
    {
        dist[v] = dist[u] + 1;
        dfs(v, adj, dist);
    }
}
int send_message(int N, int i, int Pi)
{
    if (i == 1)
    {
        p.resize(N, 0);
    }
    p[i] = Pi;
    return Pi;
}

pair<int, int> longest_path(vector<int> S)
{
    for (int i = 0; i < S.size(); i++){
        //cout << S[i] << " ";
    }
    int N = S.size();

    vector<vector<int>> adj(N, vector<int>());
    for (int i = 1; i < (int)p.size(); i++){
        adj[p[i]].push_back(i);
    }
    /*for (int i = 0; i < (int)adj.size(); i++){
        cout << i << " : ";
        for (int j = 0; j < (int)adj[i].size(); j++)
        {
            cout << adj[i][j] << " ";
        }
        cout << "\n";
    }*/
    vector<int> dist(N, 0);
    dfs(0, adj, dist);
    int max_dist = 0;
    for (int i = 0; i < (int)dist.size(); i++)
    {
        if (dist[i] > dist[max_dist])
        {
            max_dist = i;
        }
    }
    vector<int> dist2(N, 0);
    dfs(max_dist, adj, dist2);
    int max_dist2 = 0;
    for (int i = 0; i < (int)dist2.size(); i++){
        if (dist2[i] > dist[max_dist2]){
            max_dist2 = i;
        }
    }
    return {max_dist, max_dist2};
}
/*
g++ -std=gnu++20 -Wall -O2 -pipe -static -g -o main grader.cpp migrations.cpp

6
0 0 2 2 2
*/

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