Submission #72399

#	Time	Username	Problem	Language	Result	Execution time	Memory
72399		ㅋ (#118)	Aquatic Labyrinth (FXCUP3_aqua)	C++17	100 / 100	619 ms	164712 KiB

aqua

#include<bits/stdc++.h>
int ex,ey,n,w,a[1010][1010],b[1010][1010],cnt[1010][1010],sx,sy;
char s[1010][1010];
using namespace std;
# define INF 0x3f3f3f3f

// iPair ==>  Integer Pair
typedef pair<int, int> iPair;

// This class represents a directed graph using
// adjacency list representation
class Graph
{
    int V;    // No. of vertices

    // In a weighted graph, we need to store vertex
    // and weight pair for every edge
    list< pair<int, int> > *adj;

public:
    Graph(int V);  // Constructor

    // function to add an edge to graph
    void addEdge(int u, int v, int w);

    // prints shortest path from s
    void shortestPath(int s);
};

// Allocates memory for adjacency list
Graph::Graph(int V)
{
    this->V = V;
    adj = new list<iPair> [V];
}

void Graph::addEdge(int u, int v, int w)
{
    if(w==0)
    {
        u=u;
    }
    adj[u].push_back(make_pair(v, w));
}

// Prints shortest paths from src to all other vertices
void Graph::shortestPath(int src)
{
    // Create a priority queue to store vertices that
    // are being preprocessed. This is weird syntax in C++.
    // Refer below link for details of this syntax
    // https://www.geeksforgeeks.org/implement-min-heap-using-stl/
    priority_queue< iPair, vector <iPair> , greater<iPair> > pq;

    vector<int> dist(V, INF);

    pq.push(make_pair(0, src));
    dist[src] = 0;

    while (!pq.empty())
    {
        int u = pq.top().second;
        pq.pop();

        // 'i' is used to get all adjacent vertices of a vertex
        list< pair<int, int> >::iterator i;
        for (i = adj[u].begin(); i != adj[u].end(); ++i)
        {
            // Get vertex label and weight of current adjacent
            // of u.
            int v = (*i).first;
            int weight = (*i).second;

            //  If there is shorted path to v through u.
            if (dist[v] > dist[u] + weight)
            {
                // Updating distance of v
                dist[v] = dist[u] + weight;
                pq.push(make_pair(dist[v], v));
            }
        }
    }

    // Print shortest distances stored in dist[]
    int ans=min(dist[a[ex][ey]],dist[b[ex][ey]]);
    if(ans==INF) printf("-1");
    else printf("%d",ans);
}

// Driver program to test methods of graph class
int pa[4000010],pb[4000010],sav[4000010];
int main()
{
    //freopen("input.txt","r",stdin);
    int i,j;
    // create the graph given in above fugure
    int V,sw,sw2;
    scanf("%d",&n);
    V=n*n*2;
    Graph g(n*n*2);
    for(i=1;i<=n;i++)
    {
        scanf("%s",s[i]);
        for(j=n;j>=1;j--) s[i][j]=s[i][j-1]; s[i][0]=0;
        for(j=1;j<=n;j++)
        {
            if(s[i][j]=='M') sx=i, sy=j, s[i][j]='.';
            if(s[i][j]=='H') ex=i, ey=j, s[i][j]='.';
        }
    }
    for(i=1;i<=n;i++)
    {
        sw=0; sw2=0;
        for(j=1;j<=n;j++)
        {
            if(s[i][j]=='.' && s[i][j-1]!='.')
            {
                sw++;
                w++;
                pa[w]=i;
                if(sw>=2){g.addEdge(w-1,w,cnt[i][j-1]*cnt[i][j-1]); g.addEdge(w,w-1,cnt[i][j-1]*cnt[i][j-1]); sav[w]=cnt[i][j-1]*cnt[i][j-1];}
            }
            if(s[i][j]=='.') a[i][j]=w;
            if(s[i][j]=='W') cnt[i][j]=cnt[i][j-1]+1;
        }
    }
    memset(cnt,0,sizeof cnt);
    for(j=1;j<=n;j++)
    {
        sw=0; sw2=0;
        for(i=1;i<=n;i++)
        {
            if(s[i][j]=='.' && s[i-1][j]!='.')
            {
                sw++; w++; pb[w]=j;
                if(sw>=2){g.addEdge(w-1,w,cnt[i-1][j]*cnt[i-1][j]); g.addEdge(w,w-1,cnt[i-1][j]*cnt[i-1][j]); sav[w]=cnt[i-1][j]*cnt[i-1][j];}

            }
            if(s[i][j]=='.') b[i][j]=w;
            if(s[i][j]=='W') cnt[i][j]=cnt[i-1][j]+1;
        }
    }
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=n;j++)
        {
            if(s[i][j]=='.')
            {
                if(pa[a[i][j]]==pa[a[i][j]-1]) g.addEdge(b[i][j],a[i][j]-1,sav[a[i][j]]);
                if(pa[a[i][j]]==pa[a[i][j]+1]) g.addEdge(b[i][j],a[i][j]+1,sav[a[i][j]+1]);
                if(pb[b[i][j]]==pb[b[i][j]-1]) g.addEdge(a[i][j],b[i][j]-1,sav[b[i][j]]);
                if(pb[b[i][j]]==pb[b[i][j]+1]) g.addEdge(a[i][j],b[i][j]+1,sav[b[i][j]+1]);
            }
        }
    }
    int c=0;
    for(i=sy+1;i<=n;i++)
    {
        if(s[sx][i]=='.' && s[sx][i-1]=='W') g.addEdge(0,a[sx][i],c*c);
        if(s[sx][i]=='W') c++;
    }
    c=0;
    for(i=sy-1;i>=1;i--)
    {
        if(s[sx][i]=='.' && s[sx][i+1]=='W') g.addEdge(0,a[sx][i],c*c);
        if(s[sx][i]=='W') c++;
    }
    c=0;
    for(i=sx+1;i<=n;i++)
    {
        if(s[i][sy]=='.' && s[i-1][sy]=='W') g.addEdge(0,b[i][sy],c*c);
        if(s[i][sy]=='W') c++;
    }
    c=0;
    for(i=sx-1;i>=1;i--)
    {
        if(s[i][sy]=='.' && s[i+1][sy]=='W') g.addEdge(0,b[i][sy],c*c);
        if(s[i][sy]=='W') c++;
    }
    g.shortestPath(0);
    return 0;
}

Compilation message (stderr)

aqua.cpp: In function 'int main()':
aqua.cpp:104:9: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
         for(j=n;j>=1;j--) s[i][j]=s[i][j-1]; s[i][0]=0;
         ^~~
aqua.cpp:104:46: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
         for(j=n;j>=1;j--) s[i][j]=s[i][j-1]; s[i][0]=0;
                                              ^
aqua.cpp:97:9: warning: variable 'V' set but not used [-Wunused-but-set-variable]
     int V,sw,sw2;
         ^
aqua.cpp:97:14: warning: variable 'sw2' set but not used [-Wunused-but-set-variable]
     int V,sw,sw2;
              ^~~
aqua.cpp:98:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
     ~~~~~^~~~~~~~~
aqua.cpp:103:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%s",s[i]);
         ~~~~~^~~~~~~~~~~

• Subtask 1: 36 / 36
• Subtask 2: 64 / 64