Submission #920201

#	Time	Username	Problem	Language	Result	Execution time	Memory
920201		danikoynov	Land of the Rainbow Gold (APIO17_rainbow)	C++14	0 / 100	3034 ms	28852 KiB

rainbow

#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
• Subtask 2: 0 / 12
• Subtask 3: 0 / 24
• Subtask 4: 0 / 27
• Subtask 5: 0 / 26