General

# Author Problem Lang Verdict Time Memory Sent Judged
48642621 Practice:
reza
1105D - 44 GNU C++17 Wrong answer on test 38 93 ms 34252 KB 2019-01-20 18:58:12 2019-01-20 18:58:12

→ Source
#include<bits/stdc++.h>
//#include<unordered_set>
#pragma GCC optimize("Ofast")
using namespace std;
#define int long long
#define die(x) return cout << x << endl, 0
#define FI first
#define SE second
#define all(o) o.begin(), o.end()
#define endl '\n'
#define IOS ios::sync_with_stdio(0), cin.tie(0)
#define FILE freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout)
#define SZ(x) ((int)(x).size())
#define PB push_back
#define PF push_front
#define POB pop_back
#define POF pop_front
#define MP make_pair
#define FR front
#define BK back
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef map<int,int> mpi;
typedef set<int> sti;
typedef vector<pii> vii;
typedef map<pii,int> mpii;
typedef set<pii> stii;
typedef long double ld;
typedef long long ll;
int gcd(int x,int y){ return (!y ? x : gcd(y, x%y)); }
int power(int x, int y) { return (!y ? 1 : power(x, y / 2) * power(x, y / 2) * (y % 2 ? x : 1)); }
int fastMax(int x, int y) { return (((y-x)>>(32-1))&(x^y))^y; }
int fastMin(int x, int y) { return (((y-x)>>(32-1))&(x^y))^x; }
const int MAXN=1e3+10,MOD=1e9+7,INF=1e18;
const double PI = atan(1.0)*4;
int mod(int x) { return (x % MOD + MOD) % MOD; }
ll n,m,t;
ll st[10];
ll d[MAXN][MAXN];
ll cnt[10];
vii p[MAXN];
string a[MAXN];
void bfs(int src){
deque<pii>q;
char sc=src+'0';
for(auto c:p[src]){
int x=c.FI,y=c.SE;
d[x][y]=0;q.PB(MP(x,y));
}
p[src].clear();
while(!q.empty()){
int x=q.FR().FI;int y=q.FR().SE;q.POF();
// cout<<src<<"-"<<x<<" "<<y<<" "<<d[src][x][y]<<endl;
if(d[x][y]<=st[src]){
a[x][y]=sc;
//  cout<<x<<"-"<<y<<endl;
}
if(d[x][y]==st[src]){
p[src].PB(MP(x,y));
continue;
}
ll x2,y2;
x2=x;y2=y+1;
if(d[x][y]+1<d[x2][y2] && x2<=n && y2<=m && a[x2][y2]=='.'){
d[x2][y2]=d[x][y]+1;
q.PB(MP(x2,y2));
}
x2=x;y2=y-1;
if(d[x][y]+1<d[x2][y2] && x2<=n && y2<=m && a[x2][y2]=='.'){
d[x2][y2]=d[x][y]+1;
q.PB(MP(x2,y2));
}
x2=x-1;y2=y;
if(d[x][y]+1<d[x2][y2] && x2<=n && y2<=m && a[x2][y2]=='.'){
d[x2][y2]=d[x][y]+1;
q.PB(MP(x2,y2));
}
x2=x+1;y2=y;
if(d[x][y]+1<d[x2][y2] && x2<=n && y2<=m && a[x2][y2]=='.'){
d[x2][y2]=d[x][y]+1;
q.PB(MP(x2,y2));
}
}
}
int MAIN(){
cin>>n>>m>>t;
for(int i=1;i<=t;i++)cin>>st[i];
for(int i=1;i<=n;i++){
cin>>a[i];
a[i]=" "+a[i]+" ";
}
memset(d,63,sizeof(d));
for(int k=1;k<=t;k++){
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(a[i][j]==k+'0'){
p[k].PB(MP(i,j));
}
}
}
}
bool flag=1;
while(flag){
flag=0;
for(int i=1;i<=t;i++){
bfs(i);
flag=flag || SZ(p[i])>0;
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(a[i][j]!='#')cnt[a[i][j]-'0']++;
// cout<<a[i][j];
}
//  cout<<endl;
}
for(int i=1;i<=t;i++)cout<<cnt[i]<<" ";
return 0;
}
int32_t main(){
IOS;
int t=1;
//cin>>t;
while(t--)MAIN();
}

?
Time: ? ms, memory: ? KB
Verdict: ?
Input
?
Participant's output
?
?
?
?