Submission #102456
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<int> 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());
id = vector<int>(all.size());
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:38:50+0900
Task
I - Topology
User
shioshiota
Language
C++ (G++ 4.6.4)
Score
0
Code Size
3770 Byte
Status
TLE
Exec Time
1538 ms
Memory
53248 KB
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:152: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
AC
22 ms
932 KB
10
AC
24 ms
920 KB
11
AC
22 ms
804 KB
12
AC
21 ms
808 KB
13
AC
20 ms
928 KB
14
TLE
1534 ms
38944 KB
15
AC
891 ms
18680 KB
16
AC
406 ms
19492 KB
17
AC
1388 ms
17436 KB
18
TLE
1533 ms
44624 KB
19
TLE
1534 ms
44680 KB
2
AC
21 ms
800 KB
20
TLE
1534 ms
46212 KB
21
TLE
1534 ms
46468 KB
22
TLE
1538 ms
47104 KB
23
TLE
1535 ms
46972 KB
24
TLE
1534 ms
49084 KB
25
TLE
1534 ms
49016 KB
26
TLE
1534 ms
51128 KB
27
TLE
1534 ms
51064 KB
28
TLE
1536 ms
53196 KB
29
TLE
1535 ms
53248 KB
3
AC
21 ms
924 KB
30
TLE
1535 ms
48504 KB
31
TLE
1535 ms
48524 KB
32
TLE
1535 ms
48516 KB
33
AC
25 ms
1184 KB
34
AC
32 ms
1824 KB
35
AC
44 ms
2848 KB
36
AC
72 ms
4776 KB
37
AC
183 ms
3356 KB
38
AC
21 ms
804 KB
39
AC
92 ms
1956 KB
4
AC
22 ms
928 KB
40
AC
229 ms
3960 KB
41
AC
63 ms
1568 KB
42
AC
76 ms
1824 KB
43
AC
90 ms
2076 KB
44
AC
37 ms
1052 KB
45
AC
149 ms
3112 KB
46
AC
44 ms
1180 KB
47
AC
203 ms
3932 KB
48
AC
216 ms
4064 KB
49
AC
47 ms
1324 KB
5
AC
28 ms
1052 KB
50
AC
33 ms
1056 KB
6
AC
28 ms
1060 KB
7
AC
21 ms
800 KB
8
AC
22 ms
924 KB
9
AC
24 ms
796 KB