This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <stdio.h>
#include <vector>
int biggest_stadium( int N, std::vector<std::vector<int>> F ){
int nempty = 0, l, c, border, prev, minl, maxl, minc, maxc, max_fl, max_fc;
std::vector<int> fl( N, 0 ), fc( N, 0 );
minl = N;
maxl = -1;
minc = N;
maxc = -1;
for( l = 0 ; l < N ; l++ )
for( c = 0 ; c < N ; c++ )
if( !F[l][c] ){
nempty++;
fl[l]++;
fc[c]++;
minl = l < minl ? l : minl;
maxl = l > maxl ? l : maxl;
minc = c < minc ? c : minc;
maxc = c > maxc ? c : maxc;
}
for( l = 0 ; l < N ; l++ ){
prev = 1;
border = 0;
for( c = 0 ; c < N ; c++ ){
if( F[l][c] != prev ){
prev = F[l][c];
border++;
}
}
if( border > 2 )
return 1;
}
for( c = 0 ; c < N ; c++ ){
prev = 1;
border = 0;
for( l = 0 ; l < N ; l++ ){
if( F[l][c] != prev ){
prev = F[l][c];
border++;
}
}
if( border > 2 )
return 1;
}
max_fl = max_fc = 0;
for( l = 0 ; l < N ; l++ )
max_fl = fl[l] > max_fl ? fl[l] : max_fl;
for( c = 0 ; c < N ; c++ )
max_fc = fc[c] > max_fc ? fc[c] : max_fc;
if( maxl - minl + 1 != max_fl )
return 1;
if( maxc - minc + 1 != max_fc )
return 1;
return nempty;
// ignore the rest
// since initial condition is met now we can focus on couting reachable pairs
for( l = 0 ; l < N ; l++ )
for( c = 0 ; c < N ; c++ )
if( !F[l][c] ){
}
long long max_reachable = nempty;
max_reachable *= (nempty - 1);
max_reachable >>= 1; // (nempty choose 2)
long long reachable_pairs = 0;
for( l = 0 ; l < N ; l++ )
for( c = 0 ; c < N ; c++ )
if( !F[l][c] )
reachable_pairs += ((long long)fl[l]) * fc[c];
// all that is left is to count the pairs which allow 2 paths and remove them from the count
reachable_pairs -= nempty;
return reachable_pairs == max_reachable ? nempty : 1;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |