oj.uz

Submission #1028378

# Submission time Handle Problem Language Result Execution time Memory
1028378 2024-07-19T18:14:07 Z _8_8_ Land of the Rainbow Gold (APIO17_rainbow) C++17
35 / 100
 3000 ms 170380 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;
map<pair<int,int>,pair<int,int>> par;
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();
    par.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();
                par[{x,y}] = {r,c};
                // 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});
                    }
                }
            }
        }
    }
    for(auto [xx,yy]:k){
        auto [r,c] = xx;
        if(k.count({r+1,c+1}) && !k.count({r+1,c}) && !k.count({r,c+1}) && par[{r,c}] == par[{r+1,c+1}]){
            E += 2;
        }
        if(k.count({r+1,c-1}) && !k.count({r+1,c}) && !k.count({r,c-1}) && par[{r,c}] == par[{r+1,c-1}]){
            E += 2;
        }
    }
    assert(E%2==0);
    E /= 2;     
    // cout << V << ' ' << C << ' ' << E << '\n';
    return C - V + E - bf;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 344 KB Output is correct
2 Correct 170 ms 580 KB Output is correct
3 Correct 96 ms 344 KB Output is correct
4 Correct 119 ms 344 KB Output is correct
5 Correct 238 ms 604 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 186 ms 548 KB Output is correct
12 Correct 352 ms 600 KB Output is correct
13 Correct 376 ms 600 KB Output is correct
14 Correct 698 ms 1084 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct

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 3053 ms 79380 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 727 ms 67276 KB Output is correct
3 Correct 722 ms 66984 KB Output is correct
4 Correct 609 ms 57544 KB Output is correct
5 Correct 304 ms 31424 KB Output is correct
6 Correct 1087 ms 93892 KB Output is correct
7 Correct 1702 ms 135328 KB Output is correct
8 Correct 58 ms 7876 KB Output is correct
9 Correct 30 ms 4548 KB Output is correct
10 Correct 16 ms 2260 KB Output is correct
11 Correct 73 ms 9176 KB Output is correct
12 Correct 204 ms 21856 KB Output is correct
13 Correct 202 ms 21704 KB Output is correct
14 Correct 193 ms 21704 KB Output is correct
15 Correct 190 ms 21608 KB Output is correct
16 Correct 875 ms 75792 KB Output is correct
17 Correct 747 ms 68864 KB Output is correct
18 Correct 1138 ms 93632 KB Output is correct
19 Correct 1098 ms 94404 KB Output is correct
20 Correct 842 ms 76352 KB Output is correct
21 Correct 356 ms 33212 KB Output is correct
22 Correct 293 ms 27588 KB Output is correct
23 Correct 477 ms 43724 KB Output is correct
24 Correct 711 ms 59336 KB Output is correct
25 Correct 2158 ms 170180 KB Output is correct
26 Correct 2125 ms 170164 KB Output is correct
27 Correct 2111 ms 170372 KB Output is correct
28 Correct 1952 ms 165544 KB Output is correct
29 Correct 1919 ms 155296 KB Output is correct
30 Correct 1950 ms 160968 KB Output is correct
31 Correct 2095 ms 170380 KB Output is correct
32 Correct 2105 ms 170308 KB Output is correct
33 Correct 2015 ms 170184 KB Output is correct

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 344 KB Output is correct
2 Correct 170 ms 580 KB Output is correct
3 Correct 96 ms 344 KB Output is correct
4 Correct 119 ms 344 KB Output is correct
5 Correct 238 ms 604 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 186 ms 548 KB Output is correct
12 Correct 352 ms 600 KB Output is correct
13 Correct 376 ms 600 KB Output is correct
14 Correct 698 ms 1084 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Execution timed out 3032 ms 8640 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 344 KB Output is correct
2 Correct 170 ms 580 KB Output is correct
3 Correct 96 ms 344 KB Output is correct
4 Correct 119 ms 344 KB Output is correct
5 Correct 238 ms 604 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 186 ms 548 KB Output is correct
12 Correct 352 ms 600 KB Output is correct
13 Correct 376 ms 600 KB Output is correct
14 Correct 698 ms 1084 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Execution timed out 3032 ms 8640 KB Time limit exceeded
19 Halted 0 ms 0 KB -