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
?
Jury's answer
?
Checker comment
?
Diagnostics
?
Click to see test details