oj.uz

Submission #208594

# Submission time Handle Problem Language Result Execution time Memory
208594 2020-03-11T17:56:09 Z DodgeBallMan Traffic (IOI10_traffic) C++14
0 / 100
 17 ms 23804 KB 
#include<bits/stdc++.h>
#include "traffic.h"

using namespace std;
 
const int N = 1e6 + 10;
bool vis[N];
long long val[N], sum;
vector<int> g[N];
 
long long dfs( int u, int p ) {
    for( int v : g[u] ) if( v != p ) val[u] += dfs( v, u );
    return val[u];
}
 
int LocateCentre(int N, int pp[], int S[], int D[])
{
    for ( int i = 0 ; i < N ; i++ ) val[i] = pp[i], sum += val[i];
    for ( int i = 0 ; i < N - 1 ; i++ ) g[S[i]].emplace_back( D[i] ), g[D[i]].emplace_back( S[i] );
    dfs( 0, -1 );
    int ret;
    long long mn = 1e18;
    for ( int i = 0 ; i < N ; i++ ) {
        long long mx = sum - val[i];
        for( int v : g[i] ) mx = max( mx, val[v] );
        if( mn > mx ) mn = mx, ret = i;
    }
    return ret;
}

Compilation message

traffic.cpp: In function 'int LocateCentre(int, int*, int*, int*)':
traffic.cpp:28:12: warning: 'ret' may be used uninitialized in this function [-Wmaybe-uninitialized]
     return ret;
            ^~~

Subtask #1
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 23800 KB Output is correct
2 Correct 17 ms 23800 KB Output is correct
3 Incorrect 17 ms 23804 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 23800 KB Output is correct
2 Correct 17 ms 23800 KB Output is correct
3 Incorrect 17 ms 23804 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 23800 KB Output is correct
2 Correct 17 ms 23800 KB Output is correct
3 Incorrect 17 ms 23804 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 23800 KB Output is correct
2 Correct 17 ms 23800 KB Output is correct
3 Incorrect 17 ms 23804 KB Output isn't correct
4 Halted 0 ms 0 KB -