| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1086039 | underwaterkillerwhale | Land of the Rainbow Gold (APIO17_rainbow) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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;
vector<pii> nodes;
struct DSU {
map<int, int> lab, sz;
void init () {
iter (&id, nodes) lab[dd[id]] = dd[id], sz[dd[id]] = 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;
void init () {
int u = Sr, v = Sc;
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;
// cout << u <<" "<<v<<"\n";
if (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);
// cout << u <<" "<<v<<" "<<DSU.Find(u)<<" "<<DSU.Find(v)<<"\n";
if (ddE[MP(u, v)] == 0) {
++num_edges;
// cout << u << " "<<v<<"\n";
}
ddE[MP(u, v)] = 1;
}
int solution (int x, int y, int u, int 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
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 {
sub3 ::init();
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 {
sub3 :: init();
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
*/