oj.uz

Submission #1028367

# Submission time Handle Problem Language Result Execution time Memory
1028367 2024-07-19T17:37:34 Z _8_8_ Land of the Rainbow Gold (APIO17_rainbow) C++17
0 / 100
 3000 ms 90536 KB 
#include <bits/stdc++.h>
#include "rainbow.h"

using namespace std;

vector<pair<int,int>> pts;
void init(int R, int C, int sr, int sc, int M, char *S) {
    pts.push_back({sr,sc});
    for(int i = 0;i < M;i++){
        if(S[i] == 'N'){
            sr--;
        }else if(S[i] == 'S'){
            sr++;
        }else if(S[i] == 'W'){
            sc--;
        }else{
            sc++;
        }
        assert(sr <= R && sr >= 1);
        assert(sc <= C && sc >= 1);
        pts.push_back({sr,sc});
    }
    sort(pts.begin(),pts.end());
    pts.resize(unique(pts.begin(),pts.end()) - pts.begin());
}
map<pair<int,int>,bool> k,vis;
const int dx[] = {1,0,-1,0},dy[] = {0,1,0,-1};
int colour(int ar, int ac, int br, int bc) {
    // V - E + F = 1 + C -> F = 1 + C - V + E
    k.clear();
    vis.clear();
    int V = 0,E = 0,C = 0;
    for(auto [r,c]:pts){
        if(r >= ar && r <= br && c >= ac && c <= bc){
            k[{r,c}] = 1;
        }
    }
    for(int i = ar - 1;i <= br + 1;i++){
        k[{i,ac-1}] = k[{i,bc+1}] = 1;
    }
    for(int i = ac - 1;i <= bc + 1;i++){
        k[{ar-1,i}] = k[{br+1,i}] = 1;
    }
    int bf = 0;
    for(auto [xx,_y]:k){
        auto [r,c] = xx;
        if(k.count({r + 1,c}) && k.count({r,c + 1}) && k.count({r + 1,c + 1})){
            bf++;
        }
        if(!vis.count({r,c})){
            C++;
            queue<pair<int,int>> q;
            q.push({r,c});
            vis[{r,c}]=1;
            while(!q.empty()){
                V++;
                auto [x,y] = q.front();q.pop();
                // cout << x << ' ' << y << '\n';
                for(int i = 0;i < 4;i++){
                    int _x = x + dx[i],_y = y + dy[i];
                    if(k.count({_x,_y})){
                        E++;
                    }
                    if(k.count({_x,_y}) && !vis.count({_x,_y})){
                        vis[{_x,_y}]=1;
                        q.push({_x,_y});
                    }
                }
            }
        }
    }
    C=1;
    assert(E%2==0);
    E /= 2;     
    // cout << V << ' ' << C << ' ' << E << '\n';
    return C - V + E - bf;
}

Subtask #1
0 / 11.0

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

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Execution timed out 3099 ms 53584 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 348 KB Output is correct
2 Correct 510 ms 45048 KB Output is correct
3 Correct 560 ms 45000 KB Output is correct
4 Correct 469 ms 38876 KB Output is correct
5 Correct 235 ms 21440 KB Output is correct
6 Correct 816 ms 63252 KB Output is correct
7 Incorrect 1254 ms 90536 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

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

Subtask #5
0 / 26.0

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