Submission #1272086

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272086		thunopro	Dreaming (IOI13_dreaming)	C++20	18 / 100	33 ms	8028 KiB

dreaming

#include "dreaming.h"
#include<bits/stdc++.h>
using namespace std; 
#define maxn 200009 
#define fi first 
#define se second 
#define pb push_back 
#define left id<<1 
#define right id<<1|1 
#define re exit(0); 

const int INF = 2e9 ; 
const int mod = 1e9+7 ; 
typedef vector<int> vi ; 
typedef pair<int,int> pii ; 
typedef vector<pii> vii ; 

template < typename T > void chkmin ( T &a , T b ) { if ( a > b ) a = b ; } 
template < typename T > void chkmax ( T &a , T b ) { if ( a < b ) a = b ; } 

int n , m ; 

vii adjList [maxn] ; 
vi vertices ; 
bool visited [maxn] ; 
int pos , best ; 

int d [maxn] ;
int d1 [maxn] , d2 [maxn] ; 
void dfs ( int u ) 
{
    for ( auto x : vertices ) d [x] = INF ; 
    queue <int> q ; 
    q . push (u) ; d [u] = 0 ; 
    while ( !q.empty() ) 
    {
        int u = q.front() ; q.pop() ; 
        for ( auto x : adjList [u] ) 
        {
            int v = x.fi , w = x.se ; 
            if ( d [v] > d [u] + w ) q . push (v) , d [v] = d [u] + w ; 
        }
    }
    best = - 1 ; 
    for ( auto x : vertices ) if ( d [x] > best ) best = d [x] , pos = x ; 
}

void reset () 
{
    for ( int i = 1 ; i <= n ; i ++ ) adjList [i] . clear () ; 
    for ( int i = 1 ; i <= n ; i ++ ) visited [i] = false ; 
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    n = N , m = M ; 
    reset () ; 
    for ( int i = 0 ; i < m ; i ++ ) 
    {
        int u = A [i] + 1 , v = B [i] + 1 , w = T [i] ; 
        adjList [u] . push_back ({v,w}) ; 
        adjList [v] . push_back ({u,w}) ; 
    }

    vi diameter ; 
    for ( int i = 1 ; i <= n ; i ++ ) 
    {
        if ( visited [i] ) continue ; 
        vertices.clear () ; 
        queue <int> q ; 
        q . push (i) ; visited [i] = true ; 
        while ( !q.empty() ) 
        {
            int u = q.front() ; q.pop() ;
            vertices . push_back (u) ; 
            for ( auto x : adjList [u] ) 
            {
                int v = x.fi , w = x.se ; 
                if ( visited [v] == false ) 
                {
                    visited [v] = true ; 
                    q . push (v) ; 
                }
            }
        }
        dfs (vertices[0]) ; 
        dfs (pos) ; 
        for ( auto x : vertices ) d1 [x] = d [x] ; 
        dfs (pos) ; 
        for ( auto x : vertices ) d2 [x] = d [x] ; 
        int Min = INF ; 
        for ( auto x : vertices ) chkmin (Min,max(d1[x],d2[x])) ; 
        diameter . pb (Min) ; 
    }
    sort (diameter.rbegin(),diameter.rend()) ; 
    int res = diameter[0] ; 
    if ( diameter.size () >= 2 ) res = max (res,diameter[0]+diameter[1]+L) ; 
    if ( diameter.size () >= 3 ) res = max (res,diameter[1]+diameter[2]+2*L) ; 
    return res ; 
}

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