oj.uz

Submission #678653

# Submission time Handle Problem Language Result Execution time Memory
678653 2023-01-06T09:28:37 Z qwerasdfzxcl Land of the Rainbow Gold (APIO17_rainbow) C++17
35 / 100
 3000 ms 318272 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) {
    if (br <= st.begin()->first-1) return 1;
    ar = max(ar, st.begin()->first-1);
    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
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 196 ms 340 KB Output is correct
2 Correct 1046 ms 552 KB Output is correct
3 Correct 259 ms 408 KB Output is correct
4 Correct 357 ms 420 KB Output is correct
5 Correct 1370 ms 572 KB Output is correct
6 Correct 0 ms 212 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 0 ms 212 KB Output is correct
11 Correct 540 ms 444 KB Output is correct
12 Correct 1004 ms 444 KB Output is correct
13 Correct 1964 ms 812 KB Output is correct
14 Correct 2161 ms 492 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 3066 ms 91884 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 212 KB Output is correct
2 Correct 868 ms 82508 KB Output is correct
3 Correct 1002 ms 109948 KB Output is correct
4 Correct 972 ms 108400 KB Output is correct
5 Correct 424 ms 40504 KB Output is correct
6 Correct 607 ms 95504 KB Output is correct
7 Correct 1126 ms 166188 KB Output is correct
8 Correct 161 ms 10300 KB Output is correct
9 Correct 130 ms 6568 KB Output is correct
10 Correct 55 ms 3320 KB Output is correct
11 Correct 14 ms 2636 KB Output is correct
12 Correct 435 ms 39332 KB Output is correct
13 Correct 389 ms 39412 KB Output is correct
14 Correct 395 ms 39336 KB Output is correct
15 Correct 352 ms 38228 KB Output is correct
16 Correct 503 ms 84616 KB Output is correct
17 Correct 723 ms 115784 KB Output is correct
18 Correct 1052 ms 159152 KB Output is correct
19 Correct 1257 ms 173104 KB Output is correct
20 Correct 1093 ms 132676 KB Output is correct
21 Correct 311 ms 23792 KB Output is correct
22 Correct 335 ms 23152 KB Output is correct
23 Correct 77 ms 5688 KB Output is correct
24 Correct 357 ms 41828 KB Output is correct
25 Correct 2127 ms 228224 KB Output is correct
26 Correct 2339 ms 279280 KB Output is correct
27 Correct 2472 ms 318272 KB Output is correct
28 Correct 2136 ms 260728 KB Output is correct
29 Correct 1272 ms 198936 KB Output is correct
30 Correct 1669 ms 253400 KB Output is correct
31 Correct 2187 ms 280520 KB Output is correct
32 Correct 2377 ms 289416 KB Output is correct
33 Correct 2290 ms 289296 KB Output is correct

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 196 ms 340 KB Output is correct
2 Correct 1046 ms 552 KB Output is correct
3 Correct 259 ms 408 KB Output is correct
4 Correct 357 ms 420 KB Output is correct
5 Correct 1370 ms 572 KB Output is correct
6 Correct 0 ms 212 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 0 ms 212 KB Output is correct
11 Correct 540 ms 444 KB Output is correct
12 Correct 1004 ms 444 KB Output is correct
13 Correct 1964 ms 812 KB Output is correct
14 Correct 2161 ms 492 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 3066 ms 15332 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 196 ms 340 KB Output is correct
2 Correct 1046 ms 552 KB Output is correct
3 Correct 259 ms 408 KB Output is correct
4 Correct 357 ms 420 KB Output is correct
5 Correct 1370 ms 572 KB Output is correct
6 Correct 0 ms 212 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 0 ms 212 KB Output is correct
11 Correct 540 ms 444 KB Output is correct
12 Correct 1004 ms 444 KB Output is correct
13 Correct 1964 ms 812 KB Output is correct
14 Correct 2161 ms 492 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 3066 ms 15332 KB Time limit exceeded
19 Halted 0 ms 0 KB -