Submission #107443

#	Time	Username	Problem	Language	Result	Execution time	Memory
107443		DodgeBallMan	Dreaming (IOI13_dreaming)	C++14	100 / 100	162 ms	17156 KiB

dreaming

#include "dreaming.h"
#include <bits/stdc++.h>
#define pii pair<int, int>
#define x first
#define y second
using namespace std;
 
const int N = 1e5+5, INF = 1e9+1;
 
vector<pii> g[N];
bool check[N];
int ans;
pii mx1[N], mx2[N];
 
void dfs( int u, int p ) {
    check[u] = true;
    for( pii v : g[u] ) if( v.x != p ) {
        dfs( v.x, u );
        pii ret( mx1[v.x].x + v.y, v.x );
        if( ret > mx1[u] ) swap( ret, mx1[u] );
        if( ret > mx2[u] ) swap( ret, mx2[u] );
    } 
    ans = max( ans, mx1[u].x + mx2[u].x );
} 
 
void find(int u, int p, int d, int &ret) {
    int now = max( mx1[u].x, d );
    if( now < ret ) ret = now;
    for( pii v : g[u] ) if( v.x != p ) 
        find( v.x, u, max( d, mx1[u].y == v.x ? mx2[u].x : mx1[u].x ) + v.y, ret );
}
 
int travelTime( int N, int M, int L, int A[], int B[], int T[] ) {
    for( int i = 0 ; i < M ; i++ ) {
        g[A[i]].emplace_back( B[i], T[i] );
        g[B[i]].emplace_back( A[i], T[i] );
    }
    vector<int> V;
    for( int i = 0; i < N; i++ ) if( !check[i] ) {   
        dfs( i, -1 ); 
        int shortest = INF;
        find( i, -1, 0, shortest );
        V.emplace_back( shortest );
    }
    sort( V.begin(), V.end(), greater<int>() );
    if( V.size() >= 2 ) ans = max( ans, V[0] + V[1] + L );
    if( V.size() >= 3 ) ans = max( ans, V[1] + V[2] + L + L );
    return ans;
}

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