oj.uz

Submission #678647

# Submission time Handle Problem Language Result Execution time Memory
678647 2023-01-06T09:15:32 Z qwerasdfzxcl Land of the Rainbow Gold (APIO17_rainbow) C++17
0 / 100
 3000 ms 214140 KB 
#include "rainbow.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
int dx8[9] = {-1, -1, -1, 0, 1, 1, 1, 0, -1}, dy8[9] = {-1, 0, 1, 1, 1, 0, -1, -1, -1};
set<pair<int, int>> st;

void init(int R, int C, int sr, int sc, int M, char *S) {
    st.emplace(sr, sc);

    for (int i=0;i<M;i++){
        int k;
        if (S[i]=='N') k = 0;
        if (S[i]=='E') k = 1;
        if (S[i]=='S') k = 2;
        if (S[i]=='W') k = 3;

        sr += dx[k], sc += dy[k];
        st.emplace(sr, sc);
    }
}

bool valid(int x, int y, int ar, int ac, int br, int bc){
    if (st.find(make_pair(x, y))!=st.end()) return 0;
    return ar <= x && x <= br && ac <= y && y <= bc;
}

void add_edge(int x1, int y1, int x2, int y2, set<pair<int, int>> &V, map<pair<int, int>, vector<pair<int, int>>> &E, int ar, int ac, int br, int bc){
    if (valid(x1, y1, ar, ac, br, bc)) V.emplace(x1, y1);
    if (valid(x2, y2, ar, ac, br, bc)) V.emplace(x2, y2);

    if (!valid(x1, y1, ar, ac, br, bc)) return;
    if (!valid(x2, y2, ar, ac, br, bc)) return;

    auto p1 = make_pair(x1, y1);
    auto p2 = make_pair(x2, y2);
    E[p1].push_back(p2);
    E[p2].push_back(p1);

    //printf("add_edge: %d %d %d %d\n", x1, y1, x2, y2);
}

void dfs(int x, int y, map<pair<int, int>, vector<pair<int, int>>> &E, set<pair<int, int>> &visited){
    visited.emplace(x, y);
    auto p = make_pair(x, y);
    for (auto np:E[p]) if (visited.find(np)==visited.end()){
        dfs(np.first, np.second, E, visited);
    }
}

int colour(int ar, int ac, int br, int bc) {
    set<pair<int, int>> V, visited;
    map<pair<int, int>, vector<pair<int, int>>> E;

    for (int i=ar;i<br;i++){
        add_edge(i, ac, i+1, ac, V, E, ar, ac, br, bc);
        add_edge(i, bc, i+1, bc, V, E, ar, ac, br, bc);
    }

    for (int j=ac;j<bc;j++){
        add_edge(ar, j, ar, j+1, V, E, ar, ac, br, bc);
        add_edge(br, j, br, j+1, V, E, ar, ac, br, bc);
    }

    for (auto [x, y]:st){
        for (int k=0;k<8;k++){
            int nx1 = x + dx8[k], ny1 = y + dy8[k];
            int nx2 = x + dx8[k+1], ny2 = y + dy8[k+1];

            add_edge(nx1, ny1, nx2, ny2, V, E, ar, ac, br, bc);
        }
    }

    int ret = 0;
    for (auto &[x, y]:V) if (visited.find(make_pair(x, y))==visited.end()) {dfs(x, y, E, visited); ret++;}
    return ret;
}

Compilation message

rainbow.cpp: In function 'void init(int, int, int, int, int, char*)':
rainbow.cpp:20:32: warning: 'k' may be used uninitialized in this function [-Wmaybe-uninitialized]
   20 |         sr += dx[k], sc += dy[k];
      |                            ~~~~^

Subtask #1
0 / 11.0

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

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Execution timed out 3055 ms 92084 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 Correct 1100 ms 110128 KB Output is correct
3 Correct 1010 ms 109988 KB Output is correct
4 Correct 1032 ms 108492 KB Output is correct
5 Correct 532 ms 53620 KB Output is correct
6 Correct 937 ms 156156 KB Output is correct
7 Incorrect 1446 ms 214140 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

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

Subtask #5
0 / 26.0

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