Submission #1086019

#	Time	Username	Problem	Language	Result	Execution time	Memory
1086019		underwaterkillerwhale	Land of the Rainbow Gold (APIO17_rainbow)	C++17	11 / 100	3076 ms	456644 KiB

rainbow

#include <bits/stdc++.h>
#define ll              long long
#define pii             pair<int,int>
#define pll             pair<ll,ll>
#define rep(i,m,n)      for(int i=(m); i<=(n); i++)
#define reb(i,m,n)      for(int i=(m); i>=(n); i--)
#define iter(id, v)     for(auto id : v)
#define fs              first
#define se              second
#define MP              make_pair
#define pb              push_back
#define bit(msk, i)     ((msk >> i) & 1)
#define SZ(v)           (ll)v.size()
#define ALL(v)          v.begin(),v.end()

using namespace std;

mt19937_64 rd(chrono :: steady_clock :: now ().time_since_epoch().count());
ll Rand (ll l, ll r) { return uniform_int_distribution<ll> (l, r) (rd); }

const int N = 2e5 + 7;
const ll INF = 1e18;
const ll BASE = 137;
const int szBL = 350;

int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};

int n, m, Sr, Sc, nmove, Q;
string moves;

bool sub1c, sub2c, sub3c;

namespace sub1 {
    const int N1 = 50 + 7;
    int dd[N1][N1];

    void init () {
        int u = Sr, v = Sc;
        dd[u][v] = -1;
        iter (&c, moves) {
            if (c == 'N') dd[--u][v] = -1;
            else if (c == 'S') dd[++u][v] = -1;
            else if (c == 'W') dd[u][--v] = -1;
            else dd[u][++v] =-1;
        }
    }

    bool inside (int u, int v, int x, int y, int u1, int v1) {
        return u >= x && u <= u1 && v >= y && v <= v1;
    }

    int solution (int x, int y, int u, int v) {
        rep (i, 1, n)
        rep (j, 1, m) if (dd[i][j] != -1) dd[i][j] = 0;
//        rep (i, 1, n) rep (j, 1, m) cout << dd[i][j] <<" \n"[j == m];
        auto flooding = [&] (int u1, int v1, int color) {
            static queue<pii> Q;
            Q.push({u1, v1});
            dd[u1][v1] = color;
            while (!Q.empty()) {
                pii cur = Q.front();
                Q.pop();
                rep (k, 0, 3)  {
                    int ni = cur.fs + dx[k], nj = cur.se + dy[k];
                    if (inside(ni, nj, x, y, u, v) && dd[ni][nj] != -1 && dd[ni][nj] == 0) {
                        dd[ni][nj] = color;
                        Q.push({ni, nj});
                    }
                }
            }
        };

        int num_cpn = 0;
        rep (i, 1, n)
        rep (j, 1, m) {
            if (dd[i][j] == 0 && inside(i, j, x, y, u, v)) {
                ++num_cpn;
                flooding(i, j, num_cpn);
            }
        }
        return num_cpn;
    }
}

namespace sub2 {
    int dd[5][N];
    int pre[3][N];

    void init () {
        int u = Sr, v = Sc;
        dd[u][v] = -1;
        iter (&c, moves) {
            if (c == 'N') dd[--u][v] = -1;
            else if (c == 'S') dd[++u][v] = -1;
            else if (c == 'W') dd[u][--v] = -1;
            else dd[u][++v] =-1;
        }
        rep (i, 2, m) {
            pre[3][i] = pre[3][i - 1] + (dd[1][i] == dd[2][i] && dd[1][i] == -1 && dd[1][i - 1] * dd[2][i - 1] == 0);
            pre[2][i] = pre[2][i - 1] + (dd[2][i] == -1 && dd[2][i - 1] == 0);
            pre[1][i] = pre[1][i - 1] + (dd[1][i] == -1 && dd[1][i - 1] == 0);
        }
    }

    int solution (int x, int y, int u, int v) {
        if (x != u) {
            cout << pre[3][v] - pre[3][y] + (dd[1][v] == 0 || dd[2][v] == 0) <<"\n";
        }
        else {
            cout << pre[x][v] - pre[x][y] + (dd[x][v] == 0)  <<"\n";
        }
    }

}

int colour (int x, int y, int u, int v) {
    if (sub1c)
        return sub1 :: solution(x, y, u, v);
    else if (sub2c) return sub2 :: solution(x, y, u, v);
}

void init (int _n, int _m, int _Sr, int _Sc, int _nmove, char _moves[]) {
    n = _n;
    m = _m;
    Sr = _Sr;
    Sc = _Sc;
    nmove = _nmove;
    rep (i, 0, nmove - 1) moves += _moves[i];
    if (n <= 50 && m <= 50) {
        sub1 :: init();
        sub1c = 1;
    }
    else if (n == 2) {
        sub2 :: init();
        sub2c = 1;
    }
}

void solution() {
    cin >> n >> m >> nmove >> Q;
    cin >> Sr >> Sc;
    cin >> moves;
    if (n <= 50 && m <= 50) {
        sub1 :: init();
        sub1c = 1;
    }
    else if (n == 2) {
        sub2 :: init();
        sub2c = 1;
    }
    rep (i, 1, Q) {
        int x, y, u, v;
        cin >> x >> y >> u >> v;
        cout << colour (x, y, u, v) <<"\n";
    }
}

#define file(name) freopen(name".inp","r",stdin); \
freopen(name".out","w",stdout);
//int main () {
////    file("c");
//    ios_base :: sync_with_stdio(false); cin.tie(0); cout.tie(0);
//    int num_Test = 1;
////    cin >> num_Test;
//    while (num_Test--)
//        solution();
//}
/*
no bug +6
6 4 9 1
3 3
NWESSWEWS
2 3 2 3

*/

Compilation message (stderr)

rainbow.cpp: In function 'int sub2::solution(int, int, int, int)':
rainbow.cpp:113:5: warning: no return statement in function returning non-void [-Wreturn-type]
  113 |     }
      |     ^
rainbow.cpp: In function 'int colour(int, int, int, int)':
rainbow.cpp:121:1: warning: control reaches end of non-void function [-Wreturn-type]
  121 | }
      | ^
rainbow.cpp: In function 'void sub2::init()':
rainbow.cpp:100:30: warning: array subscript 3 is above array bounds of 'int [3][200007]' [-Warray-bounds]
  100 |             pre[3][i] = pre[3][i - 1] + (dd[1][i] == dd[2][i] && dd[1][i] == -1 && dd[1][i - 1] * dd[2][i - 1] == 0);
      |                         ~~~~~^
rainbow.cpp:88:9: note: while referencing 'sub2::pre'
   88 |     int pre[3][N];
      |         ^~~
rainbow.cpp:100:18: warning: array subscript 3 is above array bounds of 'int [3][200007]' [-Warray-bounds]
  100 |             pre[3][i] = pre[3][i - 1] + (dd[1][i] == dd[2][i] && dd[1][i] == -1 && dd[1][i - 1] * dd[2][i - 1] == 0);
      |             ~~~~~^
rainbow.cpp:88:9: note: while referencing 'sub2::pre'
   88 |     int pre[3][N];
      |         ^~~
rainbow.cpp: In function 'int sub2::solution(int, int, int, int)':
rainbow.cpp:108:26: warning: array subscript 3 is above array bounds of 'int [3][200007]' [-Warray-bounds]
  108 |             cout << pre[3][v] - pre[3][y] + (dd[1][v] == 0 || dd[2][v] == 0) <<"\n";
      |                     ~~~~~^
rainbow.cpp:88:9: note: while referencing 'sub2::pre'
   88 |     int pre[3][N];
      |         ^~~
rainbow.cpp:108:38: warning: array subscript 3 is above array bounds of 'int [3][200007]' [-Warray-bounds]
  108 |             cout << pre[3][v] - pre[3][y] + (dd[1][v] == 0 || dd[2][v] == 0) <<"\n";
      |                                 ~~~~~^
rainbow.cpp:88:9: note: while referencing 'sub2::pre'
   88 |     int pre[3][N];
      |         ^~~

• Subtask 1: 11 / 11
• Subtask 2: 0 / 12
• Subtask 3: 0 / 24
• Subtask 4: 0 / 27
• Subtask 5: 0 / 26