QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#227095 | #6806. Landlord | jzh# | AC ✓ | 20ms | 4096kb | C++20 | 3.0kb | 2023-10-26 21:58:47 | 2023-10-26 21:58:47 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct Point {
ll x, y;
Point() = default;
Point(ll x_, ll y_): x(x_), y(y_) {}
friend Point operator-(Point A, Point B) {return Point(A.x-B.x, A.y-B.y);}
friend ll operator*(Point A, Point B) {return A.x*B.x + A.y*B.y;}
bool operator==(Point X) {return x == X.x && y == X.y;}
void input() {
scanf("%lld%lld", &x, &y);
}
};
bool graph[100][100];
bool vis[10005];
const int MX = 9;
int fx[4][2] = {{-1,0}, {0,-1}, {0,1}, {1,0}};
bool check_in_zone(int x, int y) {
if (x<=0 || x>=MX) return false;
if (y<=0 || y>=MX) return false;
return true;
}
int id(int x, int y) {
return x*MX + y;
}
pair<int, int> coor(int v) {
return {v/MX, v%MX};
}
void dfs(int u) {
vis[u] = 1;
auto [x, y] = coor(u);
//printf("%d %d\n", x, y);
for (int f=0; f<4; f++) {
int nx = x+fx[f][0];
int ny = y+fx[f][1];
if (!check_in_zone(nx, ny)) continue;
int v = id(nx, ny);
if (!vis[v] && graph[u][v]) dfs(v);
}
}
void solve()
{
Point p[4];
map<int, int> mp[2];
int mpcnt[2] = {0};
for (int i=0; i<4; i++) {
p[i].input();
mp[0][p[i].x] = 0;
mp[1][p[i].y] = 0;
}
for (auto &[_, v]: mp[0]) v = (++mpcnt[0])+1;
for (auto &[_, v]: mp[1]) v = (++mpcnt[1])+1;
for (int i=0; i<4; i++) {
p[i].x = mp[0][p[i].x];
p[i].y = mp[1][p[i].y];
//printf("%lld %lld\n", p[i].x, p[i].y);
}
//puts(".....");
memset(graph, 0, sizeof(graph));
memset(vis, 0, sizeof(vis));
for (int i=1; i<MX; i++) {
for (int j=1; j<MX; j++) {
for (int f=0; f<4; f++) {
auto [nx, ny] = pair<int, int>(i+fx[f][0], j+fx[f][1]);
if (!check_in_zone(nx, ny)) continue;
graph[id(i, j)][id(nx, ny)] = 1;
graph[id(nx, ny)][id(i, j)] = 1;
}
}
}
for (int _=0; _<=2; _+=2) {
Point LD = p[_];
Point RU = p[_+1];
for (int x=LD.x; x<RU.x; x++) {
int y = LD.y;
graph[id(x, y)][id(x, y-1)] = 0;
graph[id(x, y-1)][id(x, y)] = 0;
y = RU.y;
graph[id(x, y)][id(x, y-1)] = 0;
graph[id(x, y-1)][id(x, y)] = 0;
}
for (int y=LD.y; y<RU.y; y++) {
int x = LD.x;
graph[id(x, y)][id(x-1, y)] = 0;
graph[id(x-1, y)][id(x, y)] = 0;
x = RU.x;
graph[id(x, y)][id(x-1, y)] = 0;
graph[id(x-1, y)][id(x, y)] = 0;
}
}
int ans = 0;
for (int i=1; i<MX; i++) for (int j=1; j<MX; j++) if (!vis[id(i, j)]) {
ans++;
dfs(id(i, j));
//puts("");
}
printf("%d\n", ans);
}
int main()
{
int ttt;
scanf("%d", &ttt);
while (ttt--) {
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3800kb
input:
3 0 0 1 1 2 2 3 4 1 0 3 2 0 1 2 3 0 0 1 1 0 0 1 1
output:
3 4 2
result:
ok 3 lines
Test #2:
score: 0
Accepted
time: 20ms
memory: 4096kb
input:
10000 399413444 601729739 838979329 605646850 176742602 192902430 399413444 601729739 19226489 2915752 27806715 977516728 4075670 1872865 19226489 925008461 45547871 393001695 58201503 713825285 18241876 197851829 45547871 713825285 237513514 504913958 868997719 543598899 134432693 110279295 2375135...
output:
3 3 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 3 3 4 3 3 4 3 3 4 3 3 4 4 3 3 5 3 3 4 3 3 5 4 3 5 4 3 3 6 3 3 4 4 5 3 3 4 3 4 3 3 3 3 3 4 3 4 3 2 3 3 4 3 3 4 3 3 4 3 3 4 3 3 4 4 3 3 5 3 3 4 4 5 3 3 4 3 4 3 3 3 3 3 4 4 4 4 4 4 4 4 3 3 4 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 4 5 6 3 4 5 ...
result:
ok 10000 lines