Submission #1086049

#	Time	Username	Problem	Language	Result	Execution time	Memory
1086049		underwaterkillerwhale	Land of the Rainbow Gold (APIO17_rainbow)	C++17	23 / 100	3051 ms	213424 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 dxx[3] = {0, 1, 1};
int dyy[3] = {1,  1, 0};

int n, m, Sr, Sc, nmove, Q;
vector<char> 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);
            }
        }
//        cout <<"hih\n";
        return num_cpn;
    }
}

namespace sub2 {
    int dd[5][N], pre[5][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) {
            return pre[3][v] - pre[3][y] + (dd[1][v] == 0 || dd[2][v] == 0);
        }
        else {
            return pre[x][v] - pre[x][y] + (dd[x][v] == 0);
        }
    }

}

namespace sub3 {
    map<pii, int> dd, ddE;
    map<int, int> ddV;
    int numn = 0, numVer = 0, num_edges = 0;

    vector<pii> nodes;

    struct DSU {
        vector<int> lab, sz;

        void init () {
            lab.resize(numn + 1);
            sz.resize(numn + 1);
            rep (i, 1, numn) lab[i] = i, sz[i] = 1;
        }

        int Find (int u) {
            return u == lab[u] ? u : lab[u] = Find(lab[u]);
        }

        void Join (int u, int v) {
            u = Find(u);
            v = Find(v);
            if (u == v) return;
            if (sz[u] < sz[v]) swap(u, v);
            sz[u] += sz[v];
            lab[v] = u;
        }
    }DSU;

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


    void init (int x, int y, int u1, int v1) {
        numn = 0;
        int u = Sr, v = Sc;
        if (inside(u, v, x - 1, y - 1, u1 + 1, v1 + 1)) {
            dd[MP(u, v)] = ++numn, nodes.pb({u, v});
        }
        iter (&c, moves) {
            if (c == 'N') --u;
            else if (c == 'S') ++u;
            else if (c == 'W') --v;
            else ++v;
            if (inside(u, v, x - 1, y - 1, u1 + 1, v1 + 1) && dd[MP(u, v)] == 0) {
                dd[MP(u, v)] = ++numn, nodes.pb({u, v});
            }
        }
    }

    void add_edge (int u, int v) {
        u = DSU.Find(u);
        v = DSU.Find(v);
        if (u == v) return;
        if (u > v) swap(u, v);
        if (ddE[MP(u, v)] == 0) ++num_edges;
        ddE[MP(u, v)] = 1;
    }

    int solution (int x, int y, int u, int v) {
        init(x, y, u, v);
        rep (i, y - 1, v + 1) {
            if (dd[{x - 1, i}] == 0) dd[{x - 1, i}] = ++numn, nodes.pb({x - 1, i});
            if (dd[{u + 1, i}] == 0) dd[{u + 1, i}] = ++numn, nodes.pb({u + 1, i});
        }
        rep (i, x - 1, u + 1) {
            if (dd[{i, y - 1}] == 0) dd[{i, y - 1}] = ++numn, nodes.pb({i, y - 1});
            if (dd[{i, v + 1}] == 0) dd[{i, v + 1}] = ++numn, nodes.pb({i, v + 1});
        }

        DSU.init();
        iter (&id, nodes) {
            pii cur = id;
            bool ok = 1;
            rep (k, 0, 2) {
                int ni = id.fs + dxx[k], nj = id.se + dyy[k];
                ok &= (dd[MP(ni, nj)] > 0);
            }
            if (ok) {
                 rep (k, 0, 2) {
                    int ni = id.fs + dxx[k], nj = id.se + dyy[k];
                    DSU.Join(dd[id], dd[MP(ni, nj)]);
                }
            }
        }

        iter (&id, nodes) {
            pii cur = id;
            rep (k, 0, 3)  {
                int ni = cur.fs + dx[k], nj = cur.se + dy[k];
                if (dd[MP(ni, nj)]) {
                    add_edge(dd[cur], dd[MP(ni, nj)]);
                }
            }
        }

        iter (&id, nodes) {
            int u = DSU.Find(dd[id]);
            if (ddV[u] == 0) ++numVer;
            ddV[u] = 1;
        }

//        cout<<"\n";
//        rep (i, 1, n + 1)
//        rep (j, 1, m + 1) cout << DSU.Find(dd[MP(i, j)]) <<"  "<<" \n"[j == m + 1];

//        cout << num_edges <<" "<< numVer <<"\n";
        return num_edges - numVer + 1;
    }

}

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);
    else
        return sub3 :: 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.pb(_moves[i]);
    if (n <= 50 && m <= 50) {
        sub1 :: init();
        sub1c = 1;
    }
    else if (n == 2) {
        sub2 :: init();
        sub2c = 1;
    }
    else {
        sub3c = 1;
    }
}

void solution() {
    cin >> n >> m >> nmove >> Q;
    cin >> Sr >> Sc;
    string S;
    cin >> S;
    rep (i, 0, nmove - 1) moves.pb(S[i]);
    if (n <= 50 && m <= 50) {
        sub1 :: init();
        sub1c = 1;
    }
    else if (n == 2) {
        sub2 :: init();
        sub2c = 1;
    }
    else {
        sub3c = 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
5 3 6 4

*/

Compilation message (stderr)

rainbow.cpp: In function 'int sub3::solution(int, int, int, int)':
rainbow.cpp:194:17: warning: variable 'cur' set but not used [-Wunused-but-set-variable]
  194 |             pii cur = id;
      |                 ^~~

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