oj.uz

Submission #129784

# Submission time Handle Problem Language Result Execution time Memory
129784 2019-07-13T08:36:08 Z davitmarg Portals (BOI14_portals) C++17
20 / 100
 47 ms 30708 KB 
/*DavitMarg*/
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <queue>
#include <iomanip>
#include <stack>
#include <cassert>
#include <iterator>
#include <bitset>
#include <fstream>
#define mod 1000000007ll
#define LL long long
#define LD long double
#define MP make_pair
#define PB push_back
#define all(v) v.begin(),v.end()
using namespace std;

int n,m,k,st,en,used[1000006],dist[1000006],mot[1000006];
pair<int,int> u[1003][1003],d[1003][1003],l[1003][1003],r[1003][1003];
vector<pair<int,int>> g[1000006];
char a[1003][1003];

int id(int y,int x)
{
	return y*m+x;
}

void print(int ind)
{
	int y,x;
    x=ind%m;
    if(!x)
		x=m;
    y=(ind-x)/m;
    cout<<"! "<<y<<" "<<x<<" d="<<dist[ind]<<endl;
}

void addNode(int a,int b,int d)
{
    if(a==b)
		return;
	g[a].PB(MP(b,d));
}

int main()
{
    cin >> n >> m;
    k=n*m+m;
    for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
		{
            scanf(" %c",a[i]+j);
            if(a[i][j]=='S')
			{
				st=id(i,j);
                a[i][j]='.';
			}
			else if(a[i][j]=='C')
			{
				en=id(i,j);
                a[i][j]='.';
			}
		}
    for(int i=1;i<=n;i++)
        a[i][0]=a[i][m+1]='#';
    for(int i=1;i<=m;i++)
        a[0][i]=a[n+1][i]='#';


    for(int i=0;i<=n;i++)
		for(int j=0;j<=m;j++)
		{
            if(a[i][j]=='#')
                u[i][j]=l[i][j]=MP(i,j);
			else
			{
				u[i][j]=u[i-1][j];
				l[i][j]=l[i][j-1];
			}
		}

    for(int i=n+1;i>=1;i--)
		for(int j=m+1;j>=1;j--)
		{
            if(a[i][j]=='#')
                d[i][j]=r[i][j]=MP(i,j);
			else
			{
				d[i][j]=d[i+1][j];
				r[i][j]=r[i][j+1];
			}
		}
    queue<int> Q;

    for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
            if(a[i-1][j]=='#' || a[i+1][j]=='#' || a[i][j-1]=='#'|| a[i][j+1]=='#')
			{
				int start=id(i,j);
				Q.push(start);
				used[start]=1;
			}

    for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
		{
			if(a[i][j]=='#')
                continue;
            if(a[i-1][j]!='#')
                addNode(id(i,j),id(i-1,j),1);
            if(a[i+1][j]!='#')
                addNode(id(i,j),id(i+1,j),1);
            if(a[i][j-1]!='#')
                addNode(id(i,j),id(i,j-1),1);
            if(a[i][j+1]!='#')
                addNode(id(i,j),id(i,j+1),1);
		}

    while(!Q.empty())
	{
		int v=Q.front();
        Q.pop();
        //print(v);
        for(int i=0;i<g[v].size();i++)
		{
			int to=g[v][i].first;
            if(used[to])
				continue;
			used[to]=1;
            mot[to]=mot[v]+1;
            Q.push(to);
		}
	}

    for(int i=1;i<=k;i++)
	{
		used[i]=0;
        dist[i]=mod;
	}

    for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
		{
			if(a[i][j]=='#')
                continue;

            if(a[i-1][j]=='#' || a[i+1][j]=='#' || a[i][j-1]=='#'|| a[i][j+1]=='#')
			{
				int y,x;
                y=u[i][j].first;
                x=u[i][j].second;
				addNode(id(i,j),id(y+1,x),mot[id(i,j)]+1);

                y=d[i][j].first;
                x=d[i][j].second;
				addNode(id(i,j),id(y-1,x),mot[id(i,j)]+1);

                y=l[i][j].first;
                x=l[i][j].second;
				addNode(id(i,j),id(y,x+1),mot[id(i,j)]+1);

                y=r[i][j].first;
                x=r[i][j].second;
				addNode(id(i,j),id(y,x-1),mot[id(i,j)]+1);
			}
		}


    priority_queue<pair<int,int>> q;
    q.push(MP(0,st));
    dist[st]=0;
    while(!q.empty())
	{
        int v=-1;
        do
		{
			v=q.top().second;
            q.pop();
		}while(used[v] && !q.empty());
        if(used[v]==1 && v==-1)
            break;
        used[v]=1;
        //print(v);
		for(int i=0;i<g[v].size();i++)
		{
            int to=g[v][i].first;
            int D=g[v][i].second;
            if(dist[to]>D+dist[v])
			{
				dist[to]=D+dist[v];
                q.push(MP(-dist[to],to));
			}
		}
	}

	cout<<dist[en]<<endl;

    return 0;
}


/*

6 6
......
.S....
......
......
......
.....C

*/

Compilation message

portals.cpp: In function 'int main()':
portals.cpp:131:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0;i<g[v].size();i++)
                     ~^~~~~~~~~~~~
portals.cpp:191:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<g[v].size();i++)
               ~^~~~~~~~~~~~
portals.cpp:59:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf(" %c",a[i]+j);
             ~~~~~^~~~~~~~~~~~~~

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 23928 KB Output is correct
2 Correct 24 ms 24056 KB Output is correct
3 Correct 24 ms 24056 KB Output is correct
4 Correct 24 ms 23928 KB Output is correct
5 Correct 24 ms 24056 KB Output is correct
6 Correct 24 ms 23996 KB Output is correct
7 Correct 24 ms 24056 KB Output is correct
8 Correct 23 ms 24056 KB Output is correct
9 Correct 24 ms 23928 KB Output is correct
10 Incorrect 24 ms 23928 KB Output isn't correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 23800 KB Output is correct
2 Correct 24 ms 24056 KB Output is correct
3 Correct 24 ms 24056 KB Output is correct
4 Correct 24 ms 23912 KB Output is correct
5 Correct 24 ms 24184 KB Output is correct
6 Correct 24 ms 24056 KB Output is correct
7 Correct 25 ms 24060 KB Output is correct
8 Correct 24 ms 24056 KB Output is correct
9 Correct 26 ms 24952 KB Output is correct
10 Incorrect 26 ms 24952 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 23800 KB Output is correct
2 Correct 24 ms 24056 KB Output is correct
3 Correct 24 ms 24056 KB Output is correct
4 Correct 23 ms 24000 KB Output is correct
5 Correct 40 ms 30200 KB Output is correct
6 Correct 42 ms 30328 KB Output is correct
7 Correct 47 ms 30708 KB Output is correct
8 Correct 38 ms 30200 KB Output is correct

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 23800 KB Output is correct
2 Correct 24 ms 24056 KB Output is correct
3 Correct 26 ms 24016 KB Output is correct
4 Correct 24 ms 23932 KB Output is correct
5 Correct 23 ms 24056 KB Output is correct
6 Correct 29 ms 24060 KB Output is correct
7 Correct 24 ms 24060 KB Output is correct
8 Correct 24 ms 24056 KB Output is correct
9 Correct 25 ms 24952 KB Output is correct
10 Incorrect 26 ms 24952 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 23928 KB Output is correct
2 Correct 24 ms 24056 KB Output is correct
3 Correct 24 ms 24056 KB Output is correct
4 Correct 24 ms 24056 KB Output is correct
5 Correct 24 ms 24056 KB Output is correct
6 Correct 23 ms 24060 KB Output is correct
7 Correct 29 ms 24056 KB Output is correct
8 Correct 24 ms 24056 KB Output is correct
9 Correct 26 ms 24952 KB Output is correct
10 Incorrect 25 ms 24952 KB Output isn't correct
11 Halted 0 ms 0 KB -