Submission #1267128

#	Time	Username	Problem	Language	Result	Execution time	Memory
1267128		nerrrmin	Migrations (IOI25_migrations)	C++20	0 / 100	272 ms	1052 KiB

migrations

#include "migrations.h"
#include<bits/stdc++.h>
#define pb push_back
using namespace std;
const int maxn = 1e4 + 10;
int n;
vector < int > g[maxn];
int mxdist, mx;
void dfs(int beg, int from, int dist)
{
    if(dist > mxdist)
    {
        mx = beg;
        mxdist = dist;
    }
    for (auto nb: g[beg])
    {
        if(nb == from)continue;
        dfs(nb, beg, dist+1);

    }
}
int mx2, mxdist2 = 0;
void dfs2(int beg, int from, int dist)
{
    if(dist > mxdist2)
    {
        mx2 = beg;
        mxdist2 = dist;
    }
    for (auto nb: g[beg])
    {
        if(nb == from)continue;
        dfs2(nb, beg, dist+1);

    }
}
int send_message(int N, int i, int Pi)
{
    n = N;
    g[Pi].pb(i);
    g[i].pb(Pi);
    dfs(0, -1, 0);

    if(i == n-2)
    {
        mxdist = 0;
        mx = 0;
        dfs(0, -1, 0);
        return mx + 1;
    }
    else if(i == n-1)
    {
        mxdist2 = 0;
        mx2 = 0;
        dfs2(n-1, -1, 0);
        if(mxdist2 > mxdist)
        {
            return n + mx2;
        }
        else
        {
            int a = mx;
            mxdist = 0;
            mx = 0;
            dfs(mx, -1, 0);
            return mx + 1;
        }
    }
    else return 0;
}

std::pair<int, int> longest_path(std::vector<int> S)
{
    n = S.size();
    std::pair < int, int > p;
    if(S[n-1] >= n)
    {

        p.first = S[n-1] - n;
        p.second = n-1;
    }
    else
    {

        p.first = S[n-2]-1;
        p.second = S[n-1]-1;
    }
  return p;
}

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