oj.uz

Submission #106443

# Submission time Handle Problem Language Result Execution time Memory
106443 2019-04-18T13:53:44 Z polyfish Land of the Rainbow Gold (APIO17_rainbow) C++14
11 / 100
 3000 ms 81912 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};

int m, n;
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;

    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());
}

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;
    }

    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);
}

//int main() {
//    freopen("rainbow.in", "r", stdin);
//    freopen("rainbow.out", "w", stdout);
//    int R, C, M, Q, sr, sc;
//    static char S[100 + 5];
//    scanf("%d %d %d %d", &R, &C, &M, &Q);
//    scanf("%d %d", &sr, &sc);
//    if (M > 0) {
//        scanf(" %s ", S);
//    }
//
//    init(R, C, sr, sc, M, S);
//
//    int query;
//    for (query = 0; query < Q; query++) {
//        int ar, ac, br, bc;
//        scanf("%d %d %d %d", &ar, &ac, &br, &bc);
//        printf("%d\n", colour(ar, ac, br, bc));
//    }
//
//    return 0;
//}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 8 ms 384 KB Output is correct
3 Correct 16 ms 512 KB Output is correct
4 Correct 15 ms 512 KB Output is correct
5 Correct 9 ms 384 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 13 ms 384 KB Output is correct
9 Correct 3 ms 256 KB Output is correct
10 Correct 2 ms 256 KB Output is correct
11 Correct 13 ms 512 KB Output is correct
12 Correct 16 ms 384 KB Output is correct
13 Correct 10 ms 512 KB Output is correct
14 Correct 10 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 2 ms 256 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 2 ms 256 KB Output is correct
3 Execution timed out 3008 ms 51032 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 709 ms 39776 KB Output is correct
3 Correct 701 ms 39672 KB Output is correct
4 Correct 564 ms 34204 KB Output is correct
5 Correct 290 ms 18844 KB Output is correct
6 Correct 1150 ms 55420 KB Output is correct
7 Incorrect 1802 ms 81912 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 8 ms 384 KB Output is correct
3 Correct 16 ms 512 KB Output is correct
4 Correct 15 ms 512 KB Output is correct
5 Correct 9 ms 384 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 13 ms 384 KB Output is correct
9 Correct 3 ms 256 KB Output is correct
10 Correct 2 ms 256 KB Output is correct
11 Correct 13 ms 512 KB Output is correct
12 Correct 16 ms 384 KB Output is correct
13 Correct 10 ms 512 KB Output is correct
14 Correct 10 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 2 ms 256 KB Output is correct
18 Execution timed out 3045 ms 5900 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 8 ms 384 KB Output is correct
3 Correct 16 ms 512 KB Output is correct
4 Correct 15 ms 512 KB Output is correct
5 Correct 9 ms 384 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 13 ms 384 KB Output is correct
9 Correct 3 ms 256 KB Output is correct
10 Correct 2 ms 256 KB Output is correct
11 Correct 13 ms 512 KB Output is correct
12 Correct 16 ms 384 KB Output is correct
13 Correct 10 ms 512 KB Output is correct
14 Correct 10 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 2 ms 256 KB Output is correct
18 Execution timed out 3045 ms 5900 KB Time limit exceeded
19 Halted 0 ms 0 KB -