oj.uz

Submission #920201

# Submission time Handle Problem Language Result Execution time Memory
920201 2024-02-02T09:04:56 Z danikoynov Land of the Rainbow Gold (APIO17_rainbow) C++14
0 / 100
 3000 ms 28852 KB 
#include "rainbow.h"
#include<bits/stdc++.h>

using namespace std;

const int inf = 1e9;

set < pair < int, int > > nodes, ver_edges, hor_edges, river;
int min_x = inf, max_x = -inf, min_y = inf, max_y = inf;

void add_node(int x, int y)
{
    nodes.insert({x, y});
}

void add_hor_edge(int x, int y)
{
    hor_edges.insert({x, y});
}

void add_ver_edge(int x, int y)
{
    ver_edges.insert({x, y});
}

void add_river(int x, int y)
{
    add_node(x, y);
    add_node(x, y + 1);
    add_node(x + 1, y);
    add_node(x + 1, y + 1);
    add_hor_edge(x, y);
    add_hor_edge(x + 1, y);
    add_ver_edge(x, y);
    add_ver_edge(x, y + 1);
    min_x = min(min_x, x);
    max_x = max(max_x, x);
    min_y = min(min_y, y);
    max_y = max(max_y, y);
    river.insert({x, y});
}

void init(int R, int C, int sr, int sc, int M, char *S)
{
    add_river(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
        if (S[i] == 'E')
            sc ++;
        else assert(false);

        add_river(sr, sc);
    }
}

int query_nodes(int ar, int ac, int br, int bc)
{
    int cnt = 0;
    for (pair < int, int > cur : nodes)
    {
        if (cur.first >= ar && cur.first <= br &&
            cur.second >= ac && cur.second <= bc)
                cnt ++;
    }
    return cnt;
}

int query_hor_edges(int ar, int ac, int br, int bc)
{
    int cnt = 0;
    for (pair < int, int > cur : hor_edges)
    {
        if (cur.first >= ar && cur.first <= br &&
            cur.second >= ac && cur.second <= bc)
                cnt ++;
    }
    return cnt;
}

int query_ver_edges(int ar, int ac, int br, int bc)
{
    int cnt = 0;
    for (pair < int, int > cur : ver_edges)
    {
        if (cur.first >= ar && cur.first <= br &&
            cur.second >= ac && cur.second <= bc)
                cnt ++;
    }
    return cnt;
}

int query_river(int ar, int ac, int br, int bc)
{
    int cnt = 0;
    for (pair < int, int > cur : river)
    {
        if (cur.first >= ar && cur.first <= br &&
            cur.second >= ac && cur.second <= bc)
                cnt ++;
    }
    return cnt;
}

int colour(int ar, int ac, int br, int bc)
{
    int V = query_nodes(ar + 1, ac + 1, br, bc) + (br - ar + 2) * 2 + (bc - ac) * 2;
    int E = 0;
    E = E + query_hor_edges(ar + 1, ac, br, bc) + (bc - ac + 1) * 2;
    E = E + query_ver_edges(ar, ac + 1, br, bc) + (br - ar + 1) * 2;
    int C = 1;
    if (ar < min_x && ac < min_y && br > max_x && bc > max_y)
        C ++;
    /// V + F = E + C + 1
    /// F = E - V + C + 1
    int F = E - V + C - query_river(ar, ac, br, bc);
    ///cout << "V " << V << " E " << E << " C " << C << endl;
    return F;
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 348 KB Output is correct
2 Correct 30 ms 600 KB Output is correct
3 Incorrect 8 ms 344 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Execution timed out 3034 ms 17488 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 344 KB Output is correct
2 Correct 219 ms 28792 KB Output is correct
3 Correct 180 ms 28752 KB Output is correct
4 Correct 195 ms 28852 KB Output is correct
5 Correct 135 ms 21588 KB Output is correct
6 Correct 57 ms 5732 KB Output is correct
7 Incorrect 109 ms 11080 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 348 KB Output is correct
2 Correct 30 ms 600 KB Output is correct
3 Incorrect 8 ms 344 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 348 KB Output is correct
2 Correct 30 ms 600 KB Output is correct
3 Incorrect 8 ms 344 KB Output isn't correct
4 Halted 0 ms 0 KB -