Submission #50980

#	Time	Username	Problem	Language	Result	Execution time	Memory
50980		SpaimaCarpatilor	Wall (CEOI14_wall)	C++17	30 / 100	2074 ms	254016 KiB

wall

#include<bits/stdc++.h>

using namespace std;

int nodes, nr, N, M, ver[409][409], hor[409][409], verC[409][409], horC[409][409], city[409][409], code[42][42][1030];
pair < int, int > cell[409 * 409];

vector < pair < int, int > > v[1700009];
long long dist[2000009];
void addEdge (int x, int y, int z)
{
    v[x].push_back ({y, z});
    v[y].push_back ({x, z});
}

priority_queue < pair < long long, int > > PQ;
long long dijkstra (int source, int destination)
{
    for (int i=1; i<=nodes; i++)
        dist[i] = 1LL << 60;
    dist[source] = 0, PQ.push ({0, source});
    while (!PQ.empty ())
    {
        auto curr = PQ.top ();
        PQ.pop ();
        if (dist[curr.second] != -curr.first) continue;
        int nod = curr.second;
        for (auto it : v[nod])
            if (dist[it.first] > dist[nod] + it.second)
                dist[it.first] = dist[nod] + it.second, PQ.push ({-dist[it.first], it.first});
    }
    return dist[destination];
}

int main ()
{
//freopen ("input", "r", stdin);
//freopen ("output", "w", stdout);

scanf ("%d %d", &N, &M);
for (int i=1; i<=N; i++)
    for (int j=1; j<=M; j++)
    {
        scanf ("%d", &city[i][j]);
        if (city[i][j])
            cell[nr ++] = {i, j};
    }
for (int i=1; i<=N; i++)
    for (int j=0; j<=M; j++)
    {
        scanf ("%d", &verC[i - 1][j]);
        for (int k=0; k<nr; k++)
            if (cell[k].first == i && cell[k].second <= j)
                ver[i - 1][j] |= 1 << k;
    }
for (int i=0; i<=N; i++)
    for (int j=0; j<M; j++)
        scanf ("%d", &horC[i][j]);
for (int i=0; i<=N; i++)
    for (int j=0; j<=M; j++)
        for (int k=0; k<(1 << nr); k++)
            code[i][j][k] = ++nodes;
for (int i=0; i<=N; i++)
    for (int j=0; j<=M; j++)
    {
        if (i < N)
        {
            for (int k=0; k<(1 << nr); k++)
                addEdge (code[i][j][k], code[i + 1][j][k ^ ver[i][j]], verC[i][j]);
        }
        if (j < M)
        {
            for (int k=0; k<(1 << nr); k++)
                addEdge (code[i][j][k], code[i][j + 1][k], horC[i][j]);
        }
    }
printf ("%lld\n", dijkstra (code[0][0][0], code[0][0][(1 << nr) - 1]));
return 0;
}

Compilation message (stderr)

wall.cpp: In function 'int main()':
wall.cpp:40:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 scanf ("%d %d", &N, &M);
 ~~~~~~^~~~~~~~~~~~~~~~~
wall.cpp:44:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf ("%d", &city[i][j]);
         ~~~~~~^~~~~~~~~~~~~~~~~~~
wall.cpp:51:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf ("%d", &verC[i - 1][j]);
         ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
wall.cpp:58:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf ("%d", &horC[i][j]);
         ~~~~~~^~~~~~~~~~~~~~~~~~~

• Subtask 1: 30 / 30
• Subtask 2: 0 / 30
• Subtask 3: 0 / 40