Submission #728871

#	Time	Username	Problem	Language	Result	Execution time	Memory
728871		Rasoul006	Dreaming (IOI13_dreaming)	C++17	100 / 100	141 ms	18552 KiB

dreaming

#include "dreaming.h"
 
#include <bits/stdc++.h>
 
#define endl "\n"
 
#define F first
 
#define S second
 
#define pb push_back
 
#define all(x) x.begin() , x.end()
 
typedef long long ll;
 
using namespace std;
 
const int N = 1e5+5;
 
const long long oo = 1e18 ;
 
vector <pair <ll,ll>> v[N] ;
 
vector <pair < ll , pair <ll , ll > > > vec ;
 
ll n , m , ans , best , mx , dis[N] , len ;
 
bool vis[N] ;
 
pair <ll,ll> dfs (ll u , ll p)
{
    vis[u] = true ;
 
    pair <ll,ll> ret = {0 , u} ;
 
    for (auto it : v[u])
    {
        if (it.F == p) continue ;
 
        pair <ll,ll> p = dfs(it.F , u) ;
 
        p.F += it.S ;
 
        ret = max(ret , p) ;
    }
 
    best = min(best , max(len - ret.F , ret.F) ) ;
 
    return ret ;
}
 
pair <ll, pair <ll,ll>> get (ll p)
{
    ll p1 , p2 ;
    p1 = dfs(p , p).S ;
    p2 = dfs(p1 , p1).S ;
    len = dfs(p1 , p1).F ;
 
    best = oo ;
 
    dfs(p1 , p1) ;
 
    return {best , {p1,p2}} ;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[])
{
    n = N ; m = M ;
 
    for (int i = 0 ; i<m ; i++)
    {
        v[B[i]].pb({A[i] , T[i]});
        v[A[i]].pb({B[i] , T[i]});
    }
 
    for (int i = 0 ; i<n ; i++)
    {
        if (!vis[i])
            vec.pb(get(i)) ;
    }
 
    while (vec.size() < 3)
        vec.pb({-oo , {-oo , -oo}}) ;
 
    sort (all(vec)); reverse(all(vec));
 
    ll bans = dfs(vec[0].S.F , 0).F ;
 
    return max({ bans , vec[0].F + vec[1].F + L , vec[1].F + vec[2].F + L + L}) ;
}

• Subtask 1: 14 / 14
• Subtask 2: 10 / 10
• Subtask 3: 23 / 23
• Subtask 4: 18 / 18
• Subtask 5: 12 / 12
• Subtask 6: 23 / 23