oj.uz

Submission #39877

# Submission time Handle Problem Language Result Execution time Memory
39877 2018-01-23T09:14:40 Z Waschbar Portals (BOI14_portals) C++14
100 / 100
 900 ms 111976 KB 
#include <bits/stdc++.h>
#define st first
#define nd second
using namespace std;

const int INF = 1e8;
const int MOD = 1e9+7;
const int MAXN = 1e3;

int n, m;
bool used[MAXN+1][MAXN+1], vis[MAXN+1][MAXN+1];
int dist[MAXN+1][MAXN+1];
vector < vector < int > > diss(MAXN+1,vector <int>(MAXN+1,INF));
char g[MAXN+1][MAXN+1];
int L[MAXN+1][MAXN+1], R[MAXN+1][MAXN+1],
    U[MAXN+1][MAXN+1], D[MAXN+1][MAXN+1];

void calc_dist() {
    multiset <pair<int,pair<int,int> > > st;
    multiset <pair<int,pair<int,int> > > :: iterator it;

    for(int i = 1; i <= n; i++)
    for(int j = 1; j <= m; j++) {
        if(g[i][j] == '#') {
            st.insert({0,{i,j}});
            dist[i][j] = 0;
        }
        else{
            if(i == 1 || j == 1 || i == n || j == m) {
                st.insert({1,{i,j}});
                dist[i][j] = 1;
            }
        }
    }

    while(!st.empty()) {
        it = st.begin();
        int x = it->nd.st;
        int y = it->nd.nd;
        vis[x][y] = 1;
        int dis = it->st;
        dist[x][y] = dis;
        st.erase(st.begin());


        if(x < n && g[x+1][y] != '#' && !vis[x+1][y])
            st.insert({dis+1,{x+1,y}});
        if(x > 1 && g[x-1][y] != '#' && !vis[x-1][y])
            st.insert({dis+1,{x-1,y}});
        if(y < m && g[x][y+1] != '#' && !vis[x][y+1])
            st.insert({dis+1,{x,y+1}});
        if(y > 1 && g[x][y-1] != '#' && !vis[x][y-1])
            st.insert({dis+1,{x,y-1}});

        while(!st.empty()){
            it = st.begin();
            if(vis[it->nd.st][it->nd.nd]) st.erase(st.begin());
            else break;
        }
    }

   /* for(int i = 1; i <= n; i++) {
    for(int j = 1; j <= m; j++)
        cout << dist[i][j] << " ";
        cout << endl;
    }*/

}


void calc_LRPU() {

      for(int i = 1; i <= n; i++){
        int x = 1, y = m;
        for(int j = 1; j <= m; j++){
            L[i][j] = x;
            if(g[i][j] == '#') x = j+1;
            R[i][m-j+1] = y;
            if(g[i][m-j+1] == '#') y = m-j;
        }
     }

     for(int j = 1; j <= m; j++){
        int x = 1, y = n;
        for(int i = 1; i <= n; i++){
            U[i][j] = x;
            if(g[i][j] == '#') x = i+1;
            D[n-i+1][j] = y;
            if(g[n-i+1][j] == '#') y = n-i;
        }
     }

}

int main() {

    ios_base::sync_with_stdio(false);
    cin.tie(0);

    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);

    cin >> n >> m;

    int x, y;
    for(int i = 1; i <= n; i++)
    for(int j = 1; j <= m; j++){
        cin >> g[i][j];
        if(g[i][j] == 'S') x = i, y = j;
    }

    calc_LRPU();
    calc_dist();

    multiset < pair< int,pair<int,int> > > st;
    multiset < pair< int,pair<int,int> > > :: iterator it;

    st.insert({0,{x,y}});

    while(!st.empty()) {
        it = st.begin();
        x = it->nd.st;
        y = it->nd.nd;
        used[x][y] = 1;
        int dis = it->st;
        diss[x][y] = dis;
        st.erase(st.begin());

        //cout << x << " " << y << " " << dis << endl;

        if(g[x][y] == 'C'){
            cout << dis; return 0;
        }

        int xx, yy;
        xx = x; yy = L[x][y];
        if(!used[xx][yy] && diss[xx][yy] > dis+dist[x][y]) {
            st.insert({dis+dist[x][y],{xx,yy}});
            diss[xx][yy] = dis+dist[x][y];
        }
        xx = x; yy = R[x][y];
        if(!used[xx][yy]&& diss[xx][yy] > dis+dist[x][y]) {
            st.insert({dis+dist[x][y],{xx,yy}});
            diss[xx][yy] = dis+dist[x][y];
        }
        xx = U[x][y]; yy = y;
        if(!used[xx][yy] && diss[xx][yy] > dis+dist[x][y]) {
            st.insert({dis+dist[x][y],{xx,yy}});
            diss[xx][yy] = dis+dist[x][y];
        }
        xx = D[x][y]; yy = y;
        if(!used[xx][yy] && diss[xx][yy] > dis+dist[x][y]) {
            st.insert({dis+dist[x][y],{xx,yy}});
            diss[xx][yy] = dis+dist[x][y];
        }

        if(x < n && g[x+1][y] != '#' && !used[x+1][y] && diss[x+1][y] > dis+1) {
            st.insert({dis+1,{x+1,y}});
            diss[x+1][y] = dis+1;
        }
        if(x > 1 && g[x-1][y] != '#' && !used[x-1][y] && diss[x-1][y] > dis+1) {
            st.insert({dis+1,{x-1,y}});
            diss[x-1][y] = dis+1;
        }
        if(y < m && g[x][y+1] != '#' && !used[x][y+1] && diss[x][y+1] > dis+1) {
            st.insert({dis+1,{x,y+1}});
            diss[x][y+1] = dis+1;
        }
        if(y > 1 && g[x][y-1] != '#' && !used[x][y-1] && diss[x][y-1] > dis+1) {
            st.insert({dis+1,{x,y-1}});
            diss[x][y-1] = dis+1;
        }
        while(!st.empty()){
            it = st.begin();
            if(used[it->nd.st][it->nd.nd]) st.erase(st.begin());
            else break;
        }

    }



}


/*
5 7
S.#....
.#..##.
.......
#.#...#
.#C.##.
10 10
....C....#
.#.#...#..
......#.##
.##.......
#....#.##.
..##.#.#..
.#...#..#.
..###..#..
#...#.#S.#
..#.......

*/

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 28552 KB Output is correct
2 Correct 3 ms 28552 KB Output is correct
3 Correct 0 ms 28552 KB Output is correct
4 Correct 1 ms 28552 KB Output is correct
5 Correct 3 ms 28552 KB Output is correct
6 Correct 3 ms 28552 KB Output is correct
7 Correct 1 ms 28552 KB Output is correct
8 Correct 1 ms 28552 KB Output is correct
9 Correct 1 ms 28552 KB Output is correct
10 Correct 2 ms 28552 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 28552 KB Output is correct
2 Correct 2 ms 28552 KB Output is correct
3 Correct 3 ms 28552 KB Output is correct
4 Correct 0 ms 28552 KB Output is correct
5 Correct 3 ms 28552 KB Output is correct
6 Correct 1 ms 28552 KB Output is correct
7 Correct 2 ms 28552 KB Output is correct
8 Correct 2 ms 28552 KB Output is correct
9 Correct 2 ms 28684 KB Output is correct
10 Correct 2 ms 28684 KB Output is correct
11 Correct 1 ms 28816 KB Output is correct
12 Correct 0 ms 28816 KB Output is correct
13 Correct 2 ms 28816 KB Output is correct
14 Correct 3 ms 28552 KB Output is correct
15 Correct 0 ms 28684 KB Output is correct
16 Correct 0 ms 28552 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 28552 KB Output is correct
2 Correct 1 ms 28552 KB Output is correct
3 Correct 1 ms 28552 KB Output is correct
4 Correct 3 ms 28552 KB Output is correct
5 Correct 31 ms 31456 KB Output is correct
6 Correct 26 ms 31456 KB Output is correct
7 Correct 25 ms 31192 KB Output is correct
8 Correct 25 ms 31984 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 28552 KB Output is correct
2 Correct 3 ms 28552 KB Output is correct
3 Correct 2 ms 28552 KB Output is correct
4 Correct 3 ms 28552 KB Output is correct
5 Correct 2 ms 28552 KB Output is correct
6 Correct 2 ms 28552 KB Output is correct
7 Correct 3 ms 28552 KB Output is correct
8 Correct 1 ms 28552 KB Output is correct
9 Correct 6 ms 28684 KB Output is correct
10 Correct 5 ms 28684 KB Output is correct
11 Correct 3 ms 28816 KB Output is correct
12 Correct 7 ms 28816 KB Output is correct
13 Correct 3 ms 28816 KB Output is correct
14 Correct 32 ms 31456 KB Output is correct
15 Correct 33 ms 31456 KB Output is correct
16 Correct 30 ms 31192 KB Output is correct
17 Correct 25 ms 30532 KB Output is correct
18 Correct 29 ms 30928 KB Output is correct
19 Correct 15 ms 28684 KB Output is correct
20 Correct 19 ms 28684 KB Output is correct
21 Correct 30 ms 31588 KB Output is correct
22 Correct 25 ms 31588 KB Output is correct
23 Correct 27 ms 31456 KB Output is correct
24 Correct 18 ms 28684 KB Output is correct
25 Correct 1 ms 28552 KB Output is correct
26 Correct 1 ms 28684 KB Output is correct
27 Correct 3 ms 28552 KB Output is correct
28 Correct 22 ms 31984 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 28552 KB Output is correct
2 Correct 3 ms 28552 KB Output is correct
3 Correct 0 ms 28552 KB Output is correct
4 Correct 0 ms 28552 KB Output is correct
5 Correct 0 ms 28552 KB Output is correct
6 Correct 3 ms 28552 KB Output is correct
7 Correct 2 ms 28552 KB Output is correct
8 Correct 1 ms 28552 KB Output is correct
9 Correct 6 ms 28684 KB Output is correct
10 Correct 2 ms 28684 KB Output is correct
11 Correct 4 ms 28816 KB Output is correct
12 Correct 2 ms 28816 KB Output is correct
13 Correct 3 ms 28816 KB Output is correct
14 Correct 32 ms 31456 KB Output is correct
15 Correct 29 ms 31456 KB Output is correct
16 Correct 43 ms 31192 KB Output is correct
17 Correct 31 ms 30532 KB Output is correct
18 Correct 29 ms 30928 KB Output is correct
19 Correct 14 ms 28684 KB Output is correct
20 Correct 17 ms 28684 KB Output is correct
21 Correct 29 ms 31588 KB Output is correct
22 Correct 22 ms 31588 KB Output is correct
23 Correct 38 ms 31456 KB Output is correct
24 Correct 900 ms 81352 KB Output is correct
25 Correct 805 ms 30400 KB Output is correct
26 Correct 388 ms 29212 KB Output is correct
27 Correct 465 ms 29212 KB Output is correct
28 Correct 858 ms 100096 KB Output is correct
29 Correct 875 ms 101812 KB Output is correct
30 Correct 839 ms 100624 KB Output is correct
31 Correct 22 ms 28684 KB Output is correct
32 Correct 542 ms 29212 KB Output is correct
33 Correct 0 ms 28552 KB Output is correct
34 Correct 1 ms 28684 KB Output is correct
35 Correct 587 ms 60100 KB Output is correct
36 Correct 2 ms 28552 KB Output is correct
37 Correct 32 ms 31984 KB Output is correct
38 Correct 773 ms 111976 KB Output is correct
39 Correct 661 ms 91120 KB Output is correct