Submission #2946178
Source Code Expand
#include<cstdio> #include<queue> #include<utility> #include<cstring> #include<stack> #include<algorithm> #include<cmath> #include<iostream> #include<map> #define MAX_N 100001 #define INF_INT 2147483647 #define INF_LL 9223372036854775807 #define REP(i,n) for(int i=0;i<(int)(n);i++) void init(int n); int find(int n); void unite(int x,int y); bool same(int x, int y); int dx[4] = {1,0,0,-1}; int dy[4] = {0,1,-1,0}; using namespace std; typedef long long int ll; typedef pair<ll,ll> P; typedef pair<P,ll> PP; bool cmp_P(const P &a,const P &b){ return a.second < b.second; } void bfs(){ } int main() { ll N,M,pos,res=0; char grid[2001][2001]; int numb[2001][2001][4]; cin >> N >> M; REP(i,N) cin >> grid[i]; REP(i,N){ pos = -1; REP(j,M){ if(grid[i][j] == '#') pos = j; else{ if(pos == -1){ numb[i][j][0] = j; }else{ numb[i][j][0] = j-pos-1; } } } } REP(i,N){ pos = -1; for(int j=M-1;j>=0;j--){ if(grid[i][j] == '#') pos = j; else{ if(pos == -1){ numb[i][j][1] = M -1 - j; }else{ numb[i][j][1] = pos -1 - j; } } } } REP(i,M){ pos = -1; for(int j=N-1;j>=0;j--){ if(grid[j][i] == '#'){ pos = j; }else{ if(pos == -1){ numb[j][i][2] = N -1 - j; }else{ numb[j][i][2] = pos -1 - j; } } } } REP(i,M){ pos = -1; REP(j,N){ if(grid[j][i] == '#') pos = j; else{ if(pos == -1){ numb[j][i][3] = j; }else{ numb[j][i][3] = j-pos-1; } } } } REP(i,N){ REP(j,M){ if(grid[i][j] == '#') continue; res += numb[i][j][0]*numb[i][j][2] + numb[i][j][0]*numb[i][j][3] + numb[i][j][1]*numb[i][j][2] + numb[i][j][1]*numb[i][j][3]; } } cout << res << endl; return 0; } int par[MAX_N]; int ranks[MAX_N]; //n要素で初期化 void init(int n){ REP(i,n){ par[i] = i; ranks[i] = 0; } } //木の根を求める int find(int x){ if(par[x] == x){ return x; }else{ return par[x] = find(par[x]); } } void unite(int x,int y){ x = find(x); y = find(y); if(x == y) return ; if(ranks[x] < ranks[y]){ par[x] = y; }else{ par[y] = x; if(ranks[x] == ranks[y]) ranks[x]++; } } bool same(int x, int y){ return find(x) == find(y); }
Submission Info
Submission Time | |
---|---|
Task | C - 右折 |
User | makss |
Language | C++14 (GCC 5.4.1) |
Score | 400 |
Code Size | 2625 Byte |
Status | AC |
Exec Time | 244 ms |
Memory | 66688 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 400 / 400 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | s1.txt, s2.txt, s3.txt |
All | 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 30.txt, 31.txt, 32.txt, 33.txt, 34.txt, 35.txt, 36.txt, s1.txt, s2.txt, s3.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
01.txt | AC | 242 ms | 66688 KB |
02.txt | AC | 243 ms | 66688 KB |
03.txt | AC | 244 ms | 66560 KB |
04.txt | AC | 242 ms | 66560 KB |
05.txt | AC | 226 ms | 66688 KB |
06.txt | AC | 226 ms | 66688 KB |
07.txt | AC | 226 ms | 66688 KB |
08.txt | AC | 225 ms | 66688 KB |
09.txt | AC | 225 ms | 66560 KB |
10.txt | AC | 226 ms | 66688 KB |
11.txt | AC | 225 ms | 66688 KB |
12.txt | AC | 228 ms | 66688 KB |
13.txt | AC | 176 ms | 66560 KB |
14.txt | AC | 172 ms | 66560 KB |
15.txt | AC | 228 ms | 66688 KB |
16.txt | AC | 227 ms | 66688 KB |
17.txt | AC | 138 ms | 5504 KB |
18.txt | AC | 136 ms | 4224 KB |
19.txt | AC | 199 ms | 66560 KB |
20.txt | AC | 200 ms | 66688 KB |
21.txt | AC | 229 ms | 66688 KB |
22.txt | AC | 227 ms | 66688 KB |
23.txt | AC | 228 ms | 66560 KB |
24.txt | AC | 227 ms | 66560 KB |
25.txt | AC | 230 ms | 66688 KB |
26.txt | AC | 225 ms | 66688 KB |
27.txt | AC | 226 ms | 66688 KB |
28.txt | AC | 224 ms | 66560 KB |
29.txt | AC | 2 ms | 2304 KB |
30.txt | AC | 2 ms | 2304 KB |
31.txt | AC | 1 ms | 2304 KB |
32.txt | AC | 1 ms | 2304 KB |
33.txt | AC | 1 ms | 2304 KB |
34.txt | AC | 1 ms | 256 KB |
35.txt | AC | 2 ms | 2304 KB |
36.txt | AC | 2 ms | 2304 KB |
s1.txt | AC | 1 ms | 2304 KB |
s2.txt | AC | 2 ms | 2304 KB |
s3.txt | AC | 1 ms | 2304 KB |