oj.uz

Submission #775038

# Submission time Handle Problem Language Result Execution time Memory
775038 2023-07-06T07:04:37 Z gagik_2007 Land of the Rainbow Gold (APIO17_rainbow) C++17
11 / 100
 3000 ms 1048576 KB 
#include "rainbow.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define ff first
#define ss second

ll ttt;
const ll INF=1e18;
const ll MOD=1e9+7;
const ll N=5007;
ll n,m,k;
vector<vector<int>>a;
vector<vector<int>>used;

void init(int R, int C, int sr, int sc, int M, char* SSSSSS) {
    string S=SSSSSS;
    n=R;
    m=C;
    a.resize(n+2, vector<int>(0, 0));
    used.resize(n+2, vector<int>(0, 0));
    for(int i=0;i<=n+1;i++){
        a[i].resize(m+2, 0);
        used[i].resize(m+2, 0);
    }
    // cout<<"a: "<<a.size()<<"x"<<a[0].size()<<endl;
    // cout<<a[6][3]<<endl;
    int i=sr,j=sc;
    a[i][j]=1;
    for(int ch:S){
        if(ch=='N'){
            i--;
        }
        if(ch=='E'){
            j++;
        }
        if(ch=='S'){
            i++;
        }
        if(ch=='W'){
            j--;
        }
        a[i][j]=1;
    }
}

vector<pii>deltas={make_pair(1,0),make_pair(-1,0),make_pair(0,1),make_pair(0,-1)};

void dfs(int i, int j, int mxi, int mni, int mxj, int mnj){
    // cout<<"DFS: "<<i<<" "<<j<<endl;
    used[i][j]=1;
    for(pii delta:deltas){
        int di=delta.ff;
        int dj=delta.ss;
        if(i+di<=mxi&&i+di>=mni&&j+dj<=mxj&&j+dj>=mnj){
            // cout<<"STUG: "<<i+di<<" "<<j+dj<<endl;
            if(!used[i+di][j+dj]&&!a[i+di][j+dj]){
                // cout<<"STUG OK"<<endl;
                dfs(i+di,j+dj,mxi,mni,mxj,mnj);
            }
            // cout<<"STUG EXAV"<<endl;
        }
    }
}

int colour(int ar, int ac, int br, int bc) {
    // cout<<"QUERY: "<<ar<<" "<<ac<<" "<<br<<" "<<bc<<endl;
    int cnt=0;
    for(int i=ar;i<=br;i++){
        for(int j=ac;j<=bc;j++){
            if(!used[i][j]&&!a[i][j]){
                cnt++;
                dfs(i,j,br,ar,bc,ac);
            }
        }
    }
    for(int i=ar;i<=br;i++){
        for(int j=ac;j<=bc;j++){
            used[i][j]=0;
        }
    }
    return cnt;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 212 KB Output is correct
2 Correct 5 ms 340 KB Output is correct
3 Correct 10 ms 492 KB Output is correct
4 Correct 10 ms 476 KB Output is correct
5 Correct 4 ms 340 KB Output is correct
6 Correct 1 ms 316 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 9 ms 476 KB Output is correct
12 Correct 9 ms 340 KB Output is correct
13 Correct 6 ms 340 KB Output is correct
14 Correct 4 ms 340 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Execution timed out 3057 ms 24028 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Runtime error 1173 ms 1048576 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 212 KB Output is correct
2 Correct 5 ms 340 KB Output is correct
3 Correct 10 ms 492 KB Output is correct
4 Correct 10 ms 476 KB Output is correct
5 Correct 4 ms 340 KB Output is correct
6 Correct 1 ms 316 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 9 ms 476 KB Output is correct
12 Correct 9 ms 340 KB Output is correct
13 Correct 6 ms 340 KB Output is correct
14 Correct 4 ms 340 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Execution timed out 3056 ms 15600 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 212 KB Output is correct
2 Correct 5 ms 340 KB Output is correct
3 Correct 10 ms 492 KB Output is correct
4 Correct 10 ms 476 KB Output is correct
5 Correct 4 ms 340 KB Output is correct
6 Correct 1 ms 316 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 9 ms 476 KB Output is correct
12 Correct 9 ms 340 KB Output is correct
13 Correct 6 ms 340 KB Output is correct
14 Correct 4 ms 340 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Execution timed out 3056 ms 15600 KB Time limit exceeded
19 Halted 0 ms 0 KB -