QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#68321 | #4788. Gravity | A_zjzj | ML | 217ms | 163348kb | C++14 | 1.3kb | 2022-12-15 19:47:03 | 2022-12-15 19:47:06 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;using ll=long long;const int N=2e3+10,M=N*N;
int n,m,k,d[N][N],id[N][N],f[M];bool vis[M];char a[N][N],b[N][N];vector<pair<int,int> >A[M];
void dfs(int x,int y){
if(id[x][y])return;id[x][y]=k;
if(a[x+1][y]=='#')dfs(x+1,y);if(a[x][y+1]=='#')dfs(x,y+1);
if(a[x-1][y]=='#')dfs(x-1,y);if(a[x][y-1]=='#')dfs(x,y-1);
}
void add(int u,int v,int w){A[u].push_back({v,w});}
void dij(){
priority_queue<pair<int,int> >q;q.push({f[0]=0,0});for(int u;!q.empty();){
u=q.top().second;q.pop();if(vis[u])continue;vis[u]=1;
for(auto [v,w]:A[u])if(f[v]>f[u]+w)f[v]=f[u]+w,q.push({-f[v],v});
}
}
int main(){
scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)scanf("%s",a[i]+1);
memset(f,0x3f,sizeof f);for(int j=1;j<=m;j++)d[n+1][j]=n+1;
for(int i=n;i>=1;i--)for(int j=1;j<=m;j++)if(a[i][j]=='#')d[i][j]=i;else d[i][j]=d[i+1][j];
for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)if(a[i][j]=='#'&&!id[i][j])k++,dfs(i,j);
for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)if(a[i][j]=='#')add(id[d[i+1][j]][j],id[i][j],d[i+1][j]-i-1);
dij();for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)b[i][j]='.';
// for(int i=1;i<=n;i++,puts(""))for(int j=1;j<=m;j++)printf("%d ",f[id(i,j)]);
for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)if(a[i][j]=='#')b[i+f[id[i][j]]][j]='#';
for(int i=1;i<=n;i++)printf("%s\n",b[i]+1);return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 21ms
memory: 114056kb
input:
10 10 .......... ..######.. ..#....#.. ..#.#..#.. ..#..#.#.. ..#....#.. ..######.. .......... ..#....#.. .......#..
output:
.......... .......... ..######.. ..#....#.. ..#....#.. ..#....#.. ..#.##.#.. ..######.. .......#.. ..#....#..
result:
ok 10 lines
Test #2:
score: 0
Accepted
time: 217ms
memory: 163348kb
input:
1583 1799 #..###..##..#.####.##.##.###..#.....##..#.#.#.#......#.....##..#.##...#.#....#..##.###...#...##.###.#.....#.##.###...#..##.#...###..#.###.#...###..#.......#...#....#.#..#...##........#.#..#..##.....###...#..#.####..####...#..##......#........#..#.##.##..#..#....##.##.##..#..##.....###....#...
output:
...............................................................................................................................................................................................................................................................................................................
result:
ok 1583 lines
Test #3:
score: 0
Accepted
time: 32ms
memory: 126656kb
input:
592 750 .......#..#.#......#.............#...............###..#..#.........#.#.......##.............#.#.#................#..#...#...#......#...#.............#..##..#.#..#..........#..##.#.#..#..#.#...#....#......####.........#..#......#...........#......#............#.###.......##.#..#.#.#...#.#.##....
output:
...............................................................................................................................................................................................................................................................................................................
result:
ok 592 lines
Test #4:
score: -100
Memory Limit Exceeded
input:
1768 1394 ###.###.#######.###.#####.####.##########################.########.###################################.#########################################.#########################.####################.##############.###########################.#######################.################.####.#.#######...