#include "rainbow.h"
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <cmath>
#include <iomanip>
#include <cassert>
#include <bitset>
#include <map>
using namespace std;
typedef pair<int, int> P;
#define rep(i, n) for (int i=0; i<(n); i++)
#define all(c) (c).begin(), (c).end()
#define uniq(c) c.erase(unique(all(c)), (c).end())
#define index(xs, x) (int)(lower_bound(all(xs), x) - xs.begin())
#define _1 first
#define _2 second
#define pb push_back
#define INF 1145141919
#define MOD 1000000007
const int DX[4] = {-1, 0, 1, 0};
const int DY[4] = {0, -1, 0, 1};
struct UF {
vector<int> U, R;
UF(int N) {
rep(i, N) U.pb(i), R.pb(1);
}
int find(int x) {if (U[x]==x)return x;return U[x]=find(U[x]); }
void unite(int x, int y) {
x=find(x),y=find(y);if(x==y)return;if(R[x]<R[y])swap(x,y);U[y]=x;R[x]+=R[y];
}
};
vector<P> pos, yoko, tate, blocks;
vector<pair<P, P> > area;
void init(int H, int W, int sr, int sc, int M, char *S) {
int y = sr-1, x = sc-1;
pos.pb(P(x, y));
blocks.pb(P(x, y));
rep(i, M) {
if (S[i] == 'N') y--;
if (S[i] == 'S') y++;
if (S[i] == 'W') x--;
if (S[i] == 'E') x++;
pos.pb(P(x, y));
pos.pb(P(x+1, y));
pos.pb(P(x, y+1));
pos.pb(P(x+1, y+1));
blocks.pb(P(x, y));
}
sort(all(pos)); uniq(pos);
sort(all(blocks)); uniq(blocks);
y = sr-1, x = sc-1;
rep(i, M) {
if (S[i] == 'N') y--;
if (S[i] == 'S') y++;
if (S[i] == 'W') x--;
if (S[i] == 'E') x++;
}
map<P, bool> ok;
for (P p : pos) ok[p] = true;
for (P repr : pos) {
int x = repr._1, y = repr._2;
if (!ok[P(x, y)]) continue;
//cout<<"------\n";
int minx=x,maxx=x,miny=y,maxy=y;
int dir = 2;
while (true) {
//cout<<x<<","<<y<<"\n";
assert(ok[P(x,y)]);
ok[P(x, y)] = false;
minx=min(minx,x);
maxx=max(maxx,x);
miny=min(miny,y);
maxy=max(maxy,y);
for (int nd=(dir+3)%4; ; nd=(nd+1)%4) {
if (ok[P(x+DX[nd], y+DY[nd])] || P(x+DX[nd], y+DY[nd]) == repr) {
dir=nd;
break;
}
}
if (dir == 0) yoko.pb(P(x-1, y));
if (dir == 2) yoko.pb(P(x, y));
if (dir == 1) tate.pb(P(x, y-1));
if (dir == 3) tate.pb(P(x, y));
x += DX[dir], y += DY[dir];
if (P(x, y) == repr) break;
}
area.pb(make_pair(P(minx,maxx), P(miny,maxy)));
}
}
int colour(int miny, int minx, int maxy, int maxx) {
miny--, minx--;
int w = maxx-minx+1, h = maxy-miny+1;
bool none = true;
for (P p : blocks) if (minx <= p._1 && p._1 < maxx && miny <= p._2 && p._2 < maxy) none = false;
if (none) return 1;
//cout<<"w="<<w<<", h="<<h<<"\n";
int e = 2*(w-1+h-1), v = 2*w+2*h-4, c = 1;
for (P p : pos) if (minx < p._1 && p._1 < maxx && miny < p._2 && p._2 < maxy) v++;
for (P p : yoko) if (minx <= p._1 && p._1 < maxx && miny < p._2 && p._2 < maxy) e++;
for (P p : tate) if (minx < p._1 && p._1 < maxx && miny <= p._2 && p._2 < maxy) e++;
for (auto p : area) if (minx < p._1._1 && p._1._2 < maxx && miny < p._2._1 && p._2._2 < maxy) c++;
//cout<<"e="<<e<<", v="<<v<<", c="<<c<<"\n";
return e-v+c-1;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3039 ms |
376 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
488 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3060 ms |
564 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3039 ms |
376 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3039 ms |
376 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
