Submission #102450
Source Code Expand
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#define REP(i, b, n) for(int i = b; i <(int)n; i++)
#define rep(i, n) REP(i, 0, n)
#define FOR(it, o) for(__typeof((o).begin()) it = (o).begin(); it != (o).end(); ++it)
using namespace std;
typedef long long ll;
const ll bx[8] = {0, 1, 1, 1, 0, -1, -1, -1};
const ll by[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
const ll wx[4] = {0, 1, 0, -1};
const ll wy[4] = {-1, 0, 1, 0};
typedef long long P;
class DSINT{
public:
vector<int> par, rank;;
inline DSINT(int n){
par = rank = vector<int>(n);
rep(i, n){
par[i] = i;
rank [i] = 0;
}
}
inline int find(int x){
if(par[x] == x)return x;
return par[x] = find(par[x]);
}
inline void unite(int x, int y){
x = find(x);
y = find(y);
if(x == y)return;
if(rank[x] < rank[y]){
par[x] = y;
}else{
par[y] = x;
if(rank[x] == rank[y])rank[x]++;
}
}
};
class DS{
public:
map<P, P> v;
map<P, int> rank;
inline DS(){
v.clear();
rank.clear();
}
inline P find(P x){
map<P, P>::iterator it = v.find(x);
if(it == v.end()){
return v[x] = x;
}
if(it->second == x)return x;
P a= find(it->second);
v.insert(it, make_pair(x, a));
return a;
}
inline void unite(P x, P y){
x = find(x);
y = find(y);
if(x == y)return;
if(rank[x] < rank[y]){
v[x] = y;
}else{
v[y] = x;
if(rank[x] == rank[y])rank[x]++;
}
}
};
P bused[100000+10];
int n;
int solve(const vector<P> &V){
vector<P> all;
vector<P> id;
rep(i, V.size()){
rep(d, 8){
P white = V[i] + (bx[d] << 32) + by[d];;
if(binary_search(bused,bused+n, white))continue;
all.push_back(white);
rep(d2, 4){
P white2 = white + (wx[d2] << 32) + wy[d2];;
if(binary_search(bused,bused+n, white2))continue;
all.push_back(white2);
}
}
}
sort(all.begin(), all.end());
P pre = -1;
int cnt = 0;
rep(i, all.size()){
if(all[i] != pre){
id[i]= cnt++;
}
pre = all[i];
}
DSINT ds(cnt);
set<P> setw;
rep(i, V.size()){
rep(d, 8){
P white = V[i] + (bx[d] << 32) + by[d];;
if(binary_search(bused,bused+n, white))continue;
setw.insert(white);
int w1 = id[lower_bound(all.begin(), all.end(), white) - all.begin()];
rep(d2, 4){
P white2 = white + (wx[d2] << 32) + wy[d2];;
if (setw.count(white2) == 0) continue;
if(binary_search(bused,bused+n, white2))continue;
int w2 = id[lower_bound(all.begin(), all.end(), white2) - all.begin()];
ds.unite(w1, w2);
}
}
}
set<P> ret;
rep(i, V.size()){
rep(d, 8){
P white = V[i] + (bx[d] << 32) + by[d];;
if(binary_search(bused,bused+n, white))continue;
int w1 = id[lower_bound(all.begin(), all.end(), white) - all.begin()];
ret.insert(ds.find(w1));
}
}
return ret.size() -1;
}
P V[100000+10];
int main(){
while(cin >> n){
DS black;
rep(i, n){
ll x, y;
scanf("%Ld %Ld", &x, &y);
V[i] = (x<<32)+y;
bused[i] = V[i];
}
sort(bused, bused+n);
rep(i, n){
rep(d, 8){
P p = V[i] + (bx[d] << 32) + by[d];
if(!binary_search(bused, bused+n, p))continue;
black.unite(V[i], p);
}
}
//black sets
map<P, vector<P> > M;
rep(i, n){
M[black.find(V[i])].push_back(V[i]);
}
int ans = 0;
FOR(it, M){
if(it->second.size() <=3)continue;
ans += solve(it->second);
}
printf("%d\n", ans);
}
}
Submission Info
Submission Time
2013-09-21 23:32:50+0900
Task
I - Topology
User
shioshiota
Language
C++ (G++ 4.6.4)
Score
0
Code Size
3727 Byte
Status
TLE
Exec Time
1586 ms
Memory
48520 KB
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:149:31: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
Judge Result
Set Name
All
Score / Max Score
0 / 100
Status
Set Name
Test Cases
All
1, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 2, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 3, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 4, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 5, 50, 6, 7, 8, 9
Case Name
Status
Exec Time
Memory
1
RE
256 ms
736 KB
10
RE
251 ms
932 KB
11
AC
21 ms
928 KB
12
AC
20 ms
804 KB
13
RE
239 ms
800 KB
14
TLE
1586 ms
32132 KB
15
RE
731 ms
18596 KB
16
AC
346 ms
19492 KB
17
RE
911 ms
17440 KB
18
RE
1222 ms
29196 KB
19
RE
1199 ms
29188 KB
2
RE
243 ms
804 KB
20
RE
1301 ms
29700 KB
21
RE
1326 ms
29704 KB
22
RE
1337 ms
46732 KB
23
RE
1429 ms
46720 KB
24
RE
1425 ms
47236 KB
25
RE
1460 ms
47320 KB
26
TLE
1516 ms
47864 KB
27
RE
1444 ms
47868 KB
28
TLE
1575 ms
48508 KB
29
TLE
1558 ms
48508 KB
3
RE
251 ms
808 KB
30
RE
1494 ms
48508 KB
31
RE
1493 ms
48512 KB
32
RE
1480 ms
48520 KB
33
AC
26 ms
1192 KB
34
AC
32 ms
1784 KB
35
AC
46 ms
2856 KB
36
AC
75 ms
4776 KB
37
RE
311 ms
3296 KB
38
RE
255 ms
804 KB
39
RE
275 ms
1952 KB
4
RE
254 ms
804 KB
40
RE
329 ms
3876 KB
41
RE
275 ms
1528 KB
42
RE
276 ms
1832 KB
43
RE
278 ms
2088 KB
44
RE
252 ms
1060 KB
45
RE
302 ms
3108 KB
46
RE
259 ms
1184 KB
47
RE
326 ms
3960 KB
48
RE
322 ms
3992 KB
49
RE
271 ms
1200 KB
5
RE
260 ms
1060 KB
50
RE
261 ms
1188 KB
6
RE
259 ms
992 KB
7
AC
23 ms
800 KB
8
RE
256 ms
928 KB
9
RE
252 ms
804 KB