Submission #29631

#	Time	Username	Problem	Language	Result	Execution time	Memory
29631		osmanorhan	Dreaming (IOI13_dreaming)	C++14	100 / 100	113 ms	15348 KiB

dreaming

#include "dreaming.h"
#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define umax( x, y ) x = max( x, y )
#define umin( x, y ) x = min( x, y )

using namespace std;

const int maxn = 100000;

typedef long long Lint;
typedef pair<int,int> ii;
typedef pair<int,ii> iii;

//first - where to go
//second.first - how much time to go
//second.second - length of longest path starting from this edge
vector<iii> w[maxn];
vector<int> v, ans;
bool used[maxn];

int dfs( int n, int back ) {
    int ret = 0;
    v.pb( n );
    used[n] = 1;
    for(int i=0;i<w[n].size();i++)
        if( w[n][i].fi != back ) umax( ret, (w[n][i].se.se = (w[n][i].se.fi + dfs( w[n][i].fi, n ))) );
    return ret;
}

bool comp( const iii &a, const iii &b ) {
    return a.se.se > b.se.se;
}

void dfs2( int n, int back, int s ) {
    for(int i=0;i<w[n].size();i++)
        if( w[n][i].fi == back ) w[n][i].se.se = s;
    sort( w[n].begin(), w[n].end(), comp );
    for(int i=0;i<w[n].size();i++)
        if( w[n][i].fi != back ) {
            if( i ) dfs2( w[n][i].fi, n, w[n][i].se.fi+w[n][0].se.se );
            else dfs2( w[n][i].fi, n, ( w[n].size()==1 ? 0:w[n][1].se.se ) + w[n][i].se.fi );
        }
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    for(int i=0;i<M;i++) {
        w[ A[i] ].pb( iii( B[i], ii( T[i], 0 ) ) );
        w[ B[i] ].pb( iii( A[i], ii( T[i], 0 ) ) );
    }

    int ret = 0;
    for(int i=0;i<N;i++)
        if( !used[i] ) {
            v.clear();
            dfs( i, i );
            dfs2( i, i, 0 );
            int mini = 1e9;
            while( v.size() ) {
                int maxi = 0, n = v[v.size()-1];
                for(int j=0;j<w[n].size();j++) umax( maxi, w[n][j].se.se );
                umin( mini, maxi );
                umax( ret, maxi );
                v.pop_back();
            }
            ans.pb( mini );
        }

    sort( ans.begin(), ans.end() );
    reverse( ans.begin(), ans.end() );
    if( ans.size() >= 2 ) umax( ret, ans[0]+ans[1]+L );
    if( ans.size() >= 3 ) umax( ret, ans[1]+ans[2]+L+L );

    return ret;
}

Compilation message (stderr)

dreaming.cpp: In function 'int dfs(int, int)':
dreaming.cpp:28:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<w[n].size();i++)
                 ~^~~~~~~~~~~~
dreaming.cpp: In function 'void dfs2(int, int, int)':
dreaming.cpp:38:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<w[n].size();i++)
                 ~^~~~~~~~~~~~
dreaming.cpp:41:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<w[n].size();i++)
                 ~^~~~~~~~~~~~
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:63:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for(int j=0;j<w[n].size();j++) umax( maxi, w[n][j].se.se );
                             ~^~~~~~~~~~~~

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