oj.uz

Submission #29630

# Submission time Handle Problem Language Result Execution time Memory
29630 2017-07-20T09:19:25 Z osmanorhan Dreaming (IOI13_dreaming) C++14
18 / 100
 85 ms 11384 KB 
#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 ) ) );
    }

    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 );
                v.pop_back();
            }
            ans.pb( mini );
        }

    sort( ans.begin(), ans.end() );
    reverse( ans.begin(), ans.end() );
    int ret = ans[0];
    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

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:62: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
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 85 ms 11384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 85 ms 11384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 85 ms 11384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 5504 KB Output is correct
2 Correct 42 ms 5496 KB Output is correct
3 Correct 28 ms 5504 KB Output is correct
4 Correct 33 ms 5504 KB Output is correct
5 Correct 35 ms 5452 KB Output is correct
6 Correct 47 ms 5880 KB Output is correct
7 Correct 33 ms 5624 KB Output is correct
8 Correct 31 ms 5504 KB Output is correct
9 Correct 24 ms 5504 KB Output is correct
10 Correct 28 ms 5632 KB Output is correct
11 Correct 4 ms 2688 KB Output is correct
12 Correct 7 ms 3452 KB Output is correct
13 Correct 8 ms 3452 KB Output is correct
14 Correct 8 ms 3452 KB Output is correct
15 Correct 7 ms 3452 KB Output is correct
16 Correct 7 ms 3452 KB Output is correct
17 Correct 7 ms 3452 KB Output is correct
18 Correct 8 ms 3452 KB Output is correct
19 Correct 7 ms 3452 KB Output is correct
20 Correct 4 ms 2688 KB Output is correct
21 Correct 4 ms 2688 KB Output is correct
22 Correct 4 ms 2688 KB Output is correct
23 Correct 8 ms 3452 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 85 ms 11384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 85 ms 11384 KB Output isn't correct
2 Halted 0 ms 0 KB -