oj.uz

Submission #106456

# Submission time Handle Problem Language Result Execution time Memory
106456 2019-04-18T14:25:17 Z polyfish Land of the Rainbow Gold (APIO17_rainbow) C++14
11 / 100
 3000 ms 81708 KB 
#include "rainbow.h"
#include <bits/stdc++.h>
using namespace std;

#define debug(x) cerr << #x << " = " << x << '\n';
#define BP() cerr << "OK!\n";
#define PR(A, n) {cerr << #A << " = "; for (int _=1; _<=n; ++_) cerr << A[_] << ' '; cerr << '\n';}
#define PR0(A, n) {cerr << #A << " = "; for (int _=0; _<n; ++_) cerr << A[_] << ' '; cerr << '\n';}
#define FILE_NAME "data"

const int X[] = {-1, 0, 1, 0};
const int Y[] = {0, -1, 0, 1};
const int INF = 1e9;

int m, n, min_x, max_x, min_y, max_y;
vector<pair<int, int> > snake;
bool visited[52][52];

void init(int R, int C, int sr, int sc, int M, char *S) {
    m = R;
    n = C;
    max_x = max_y = -INF;
    min_x = min_y = INF;

    snake.resize(M+1);
    snake[0] = {sr, sc};
    for (int i=1; i<=M; ++i) {
        snake[i] = snake[i-1];
        if (S[i-1]=='N')
            --snake[i].first;
        else if (S[i-1]=='S')
            ++snake[i].first;
        else if (S[i-1]=='W')
            --snake[i].second;
        else
            ++snake[i].second;
    }

    sort(snake.begin(), snake.end());
    snake.resize(unique(snake.begin(), snake.end()) - snake.begin());
    for (auto p : snake) {
        min_x = min(min_x, p.first);
        max_x = max(max_x, p.first);
        min_y = min(min_y, p.second);
        max_y = max(max_y, p.second);
    }
}

void visit(int u, int v, int x1, int y1, int x2, int y2) {
    visited[u][v] = true;

    for (int i=0; i<4; ++i) {
        int p = u + X[i], q = v + Y[i];
        if (x1<=p && p<=x2 && y1<=q && q<=y2 && !visited[p][q])
            visit(p, q, x1, y1, x2, y2);
    }
}

int subtask1(int x1, int y1, int x2, int y2) {
    memset(visited, false, sizeof(visited));

    for (auto p : snake)
        visited[p.first][p.second] = true;

    int res = 0;

    for (int i=x1; i<=x2; ++i) {
        for (int j=y1; j<=y2; ++j) {
            if (!visited[i][j]) {
                ++res;
                visit(i, j, x1, y1, x2, y2);
            }
        }
    }

    return res;
}

int subtask3(int x1, int y1, int x2, int y2) {
    set<pair<int, int> > v;
    set<pair<pair<int, int>, pair<int, int> > > e;

    ///find all vertices
    for (int i=y1-1; i<=y2+1; ++i) {
        v.insert({x1-1, i});
        v.insert({x2+1, i});
    }
    for (int i=x1-1; i<=x2+1; ++i) {
        v.insert({i, y1-1});
        v.insert({i, y2+1});
    }
    for (auto p : snake) {
        if (x1<=p.first && p.first<=x2 && y1<=p.second && p.second<=y2)
            v.insert(p);
    }
//    debug(v.size());

    ///find all edges
    for (auto p : v) {
        for (int i=0; i<4; ++i) {
            pair<int, int> q(p.first+X[i], p.second+Y[i]);
            if (v.count(q))
                e.insert({min(p, q), max(p, q)});
        }
    }
//    debug(e.size());

    int res = (int)e.size() - (int)v.size() + 1;

    for (auto p : v) {
        if (v.count({p.first+1, p.second}) && v.count({p.first, p.second+1})
            && v.count({p.first+1, p.second+1}))
            --res;
    }

    if (x1<min_x && max_x<x2 && y1<min_y && max_y<y2)
        ++res;

    return res;
}

int colour(int x1, int y1, int x2, int y2) {
    if (m<=50 && n<=50)
        return subtask1(x1, y1, x2, y2);
    else
        return subtask3(x1, y1, x2, y2);
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 7 ms 384 KB Output is correct
3 Correct 18 ms 512 KB Output is correct
4 Correct 15 ms 512 KB Output is correct
5 Correct 7 ms 384 KB Output is correct
6 Correct 2 ms 256 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 256 KB Output is correct
9 Correct 2 ms 256 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 13 ms 556 KB Output is correct
12 Correct 12 ms 512 KB Output is correct
13 Correct 9 ms 384 KB Output is correct
14 Correct 8 ms 384 KB Output is correct
15 Correct 2 ms 384 KB Output is correct
16 Correct 2 ms 256 KB Output is correct
17 Correct 3 ms 384 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Execution timed out 3091 ms 51028 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 749 ms 39512 KB Output is correct
3 Correct 739 ms 39672 KB Output is correct
4 Correct 573 ms 34040 KB Output is correct
5 Correct 297 ms 18820 KB Output is correct
6 Correct 1134 ms 55272 KB Output is correct
7 Incorrect 1789 ms 81708 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 7 ms 384 KB Output is correct
3 Correct 18 ms 512 KB Output is correct
4 Correct 15 ms 512 KB Output is correct
5 Correct 7 ms 384 KB Output is correct
6 Correct 2 ms 256 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 256 KB Output is correct
9 Correct 2 ms 256 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 13 ms 556 KB Output is correct
12 Correct 12 ms 512 KB Output is correct
13 Correct 9 ms 384 KB Output is correct
14 Correct 8 ms 384 KB Output is correct
15 Correct 2 ms 384 KB Output is correct
16 Correct 2 ms 256 KB Output is correct
17 Correct 3 ms 384 KB Output is correct
18 Execution timed out 3085 ms 5576 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 7 ms 384 KB Output is correct
3 Correct 18 ms 512 KB Output is correct
4 Correct 15 ms 512 KB Output is correct
5 Correct 7 ms 384 KB Output is correct
6 Correct 2 ms 256 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 256 KB Output is correct
9 Correct 2 ms 256 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 13 ms 556 KB Output is correct
12 Correct 12 ms 512 KB Output is correct
13 Correct 9 ms 384 KB Output is correct
14 Correct 8 ms 384 KB Output is correct
15 Correct 2 ms 384 KB Output is correct
16 Correct 2 ms 256 KB Output is correct
17 Correct 3 ms 384 KB Output is correct
18 Execution timed out 3085 ms 5576 KB Time limit exceeded
19 Halted 0 ms 0 KB -