제출 #1369578

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1369578		edga1	Migrations (IOI25_migrations)	C++20	20 / 100	22 ms	1728 KiB

migrations

#include "migrations.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define ll long long
using namespace std;

const int N=10005;
vector<int> g[N];
int p2,ld,n;

pair<int,int> ft(int v, int p, int dz){
    int bdz=dz,bv=v;
    for(auto u : g[v]){
        if(u==p) continue;
        auto au=ft(u,v,dz+1);
        if(au.se>bdz){
            bdz=au.se;
            bv=au.fi;
        }
    }
    return {bv,bdz};
}

pair<int,pair<int,int>> fd(){
    auto t1=ft(0,0,0);
    auto t2=ft(t1.fi,t1.fi,0);
    return {t2.se,{t1.fi,t2.fi}};
}

int send_message(int n, int i, int Pi) {
    g[i].pb(Pi);
    g[Pi].pb(i);
    if(i==n-2){
        auto au=fd();
        ld=au.fi;
        p2=au.se.fi;
        return au.se.se;
    }
    if(i==n-1){
        auto au=fd();
        if(au.fi==ld) return p2;
        if(au.se.fi!=n-1) return au.se.fi+n;
        return au.se.se+n;
    }
    return 0;
}

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

• 서브태스크 0: 0 / 0
• 서브태스크 1: 10 / 30
• 서브태스크 2: 10.0003 / 70