oj.uz

Submission #939208

# Submission time Handle Problem Language Result Execution time Memory
939208 2024-03-06T06:46:36 Z WanWan Soccer Stadium (IOI23_soccer) C++17
2 / 100
 1 ms 600 KB 
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
void debug_out() {cerr<<endl;}
template <typename Head, typename... Tail>
void debug_out(Head _H, Tail... _T) {cerr<<" "<<to_string(_H);debug_out(_T...);}
#define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:",debug_out(__VA_ARGS__)
#else
#define debug(...)
#endif
const int MAXN = 2005;
const int inf=1000000500ll;
const long long oo =1000000000000000500ll;
const int MOD = (int)1e9;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef pair<int,int> pi; 
vector<int> row[MAXN], col[MAXN];
struct ufds_{
    int p[MAXN];
    ufds_(){
        iota(p,p+MAXN,0);
    }
    int find(int x){
        if(x==p[x])return x;
        else return p[x]=find(p[x]);
    }
    void merge(int x, int y){
        x=find(x);y=find(y);
        p[y]=x;
    }
}ufds;
int dx[]={-1,0,1,0};
int dy[]={0,1,0,-1};
int n;
int get(int x, int y){
    return x*n+y;
}
int biggest_stadium(int N, std::vector<std::vector<int>> V)
{
    n=N;
    int cnt=0;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(V[i][j] == 0){
                ++cnt;
                for(int k=0;k<3;k++){
                    int nx=i+dx[k];
                    int ny=j+dy[k];
                    if(nx<0 || nx>=n ||ny<0 || ny>=n || V[nx][ny])continue;
                    ufds.merge(get(i,j),get(nx,ny));
                }
            }
        }
    }
    unordered_set<int>os;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(V[i][j] == 0)os.insert(ufds.find(get(i,j)));
        }
    }
    if(os.size() > 1)return 0;

    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(V[i][j])row[i].push_back(j);
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(V[i][j])col[j].push_back(i);
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(V[i][j] == 0){
                if(upper_bound(row[i].begin(),row[i].end(),j) != row[i].end() && upper_bound(col[j].begin(),col[j].end(),i) != col[j].end()){
                    int nx=*upper_bound(row[i].begin(),row[i].end(),j);
                    int ny=*upper_bound(col[j].begin(),col[j].end(),i);
                    if(V[nx][ny] == 0)return 0;
                }
                if(upper_bound(row[i].begin(),row[i].end(),j) != row[i].end() && lower_bound(col[j].begin(),col[j].end(),i) != col[j].begin()){
                    int nx=*upper_bound(row[i].begin(),row[i].end(),j);
                    int ny=*prev(lower_bound(col[j].begin(),col[j].end(),i));
                    if(V[nx][ny] == 0)return 0;
                }
                if(lower_bound(row[i].begin(),row[i].end(),j) != row[i].begin() && upper_bound(col[j].begin(),col[j].end(),i) != col[j].end()){
                    int nx=*prev(lower_bound(row[i].begin(),row[i].end(),j));
                    int ny=*upper_bound(col[j].begin(),col[j].end(),i);
                    if(V[nx][ny] == 0)return 0;
                }
                if(lower_bound(row[i].begin(),row[i].end(),j) != row[i].begin() && lower_bound(col[j].begin(),col[j].end(),i) != col[j].begin()){
                    int nx=*prev(lower_bound(row[i].begin(),row[i].end(),j));
                    int ny=*prev(lower_bound(col[j].begin(),col[j].end(),i));
                    if(V[nx][ny] == 0)return 0;
                }

            }
        }
    }

    return cnt;
}

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 348 KB partial

Subtask #1
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB ok
2 Correct 0 ms 348 KB ok
3 Correct 1 ms 348 KB ok
4 Correct 0 ms 600 KB ok
5 Correct 0 ms 348 KB ok
6 Incorrect 0 ms 348 KB wrong
7 Halted 0 ms 0 KB -

Subtask #2
2.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB ok
2 Correct 0 ms 348 KB ok
3 Partially correct 0 ms 344 KB partial
4 Partially correct 0 ms 348 KB partial
5 Partially correct 0 ms 544 KB partial
6 Partially correct 0 ms 348 KB partial
7 Partially correct 0 ms 348 KB partial
8 Correct 1 ms 348 KB ok
9 Correct 0 ms 348 KB ok
10 Partially correct 1 ms 348 KB partial
11 Partially correct 0 ms 348 KB partial
12 Partially correct 0 ms 348 KB partial
13 Correct 0 ms 540 KB ok

Subtask #3
0.0 / 22.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 348 KB partial
2 Correct 0 ms 348 KB ok
3 Correct 0 ms 348 KB ok
4 Partially correct 0 ms 344 KB partial
5 Partially correct 0 ms 348 KB partial
6 Partially correct 0 ms 544 KB partial
7 Partially correct 0 ms 348 KB partial
8 Partially correct 0 ms 348 KB partial
9 Correct 1 ms 348 KB ok
10 Correct 0 ms 348 KB ok
11 Partially correct 1 ms 348 KB partial
12 Partially correct 0 ms 348 KB partial
13 Partially correct 0 ms 348 KB partial
14 Correct 0 ms 540 KB ok
15 Incorrect 0 ms 600 KB wrong
16 Halted 0 ms 0 KB -

Subtask #4
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 348 KB partial
2 Correct 0 ms 348 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 1 ms 348 KB ok
5 Correct 0 ms 600 KB ok
6 Partially correct 0 ms 344 KB partial
7 Partially correct 0 ms 348 KB partial
8 Partially correct 0 ms 544 KB partial
9 Partially correct 0 ms 348 KB partial
10 Partially correct 0 ms 348 KB partial
11 Correct 1 ms 348 KB ok
12 Correct 0 ms 348 KB ok
13 Partially correct 1 ms 348 KB partial
14 Partially correct 0 ms 348 KB partial
15 Partially correct 0 ms 348 KB partial
16 Correct 0 ms 540 KB ok
17 Incorrect 0 ms 600 KB wrong
18 Halted 0 ms 0 KB -

Subtask #5
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 348 KB partial
2 Correct 0 ms 348 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 1 ms 348 KB ok
5 Correct 0 ms 600 KB ok
6 Partially correct 0 ms 344 KB partial
7 Partially correct 0 ms 348 KB partial
8 Partially correct 0 ms 544 KB partial
9 Partially correct 0 ms 348 KB partial
10 Partially correct 0 ms 348 KB partial
11 Correct 1 ms 348 KB ok
12 Correct 0 ms 348 KB ok
13 Partially correct 1 ms 348 KB partial
14 Partially correct 0 ms 348 KB partial
15 Partially correct 0 ms 348 KB partial
16 Correct 0 ms 540 KB ok
17 Incorrect 0 ms 600 KB wrong
18 Halted 0 ms 0 KB -

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 348 KB partial
2 Correct 0 ms 348 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 1 ms 348 KB ok
5 Correct 0 ms 600 KB ok
6 Correct 0 ms 348 KB ok
7 Incorrect 0 ms 348 KB wrong
8 Halted 0 ms 0 KB -