Submission #1267668

#	Time	Username	Problem	Language	Result	Execution time	Memory
1267668		nerrrmin	Migrations (IOI25_migrations)	C++20	20 / 100	32 ms	1060 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 = 0, mx = 0;
int realdist = 0, realmx = 0;
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);

    }
}
void dfs_real(int beg, int from, int dist)
{
    if(dist > realdist)
    {
        realmx = beg;
        realdist = dist;
    }
    for (auto nb: g[beg])
    {
        if(nb == from)continue;
        dfs_real(nb, beg, dist+1);

    }
}
int mx2 = 0, 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);


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

           // assert(mxdist > mxdist2);
            return n + mx2 + 1;
        }
        else
        {
            int a = mx;
            mxdist = 0;
            mx = 0;
            dfs(a, -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 - 1;
        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: 10 / 30
• Subtask 2: 10.0002 / 70