Submission #676459

#	Time	Username	Problem	Language	Result	Execution time	Memory
676459		vjudge1	Wall (CEOI14_wall)	C++17	30 / 100	1381 ms	199016 KiB

wall

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,int> pli;
struct edge {
    int j, x; ll w;
    edge(){}
    edge(int j, ll w, int x):j(j),w(w),x(x){}
};
int n, m, p;
int arr[50][50];
ll dis[2100000];
ll INF = (1LL<<60);
vector<edge> lis[2100000];
int val(int x, int y) {return x*(m+1)+y;}
int rval(int val, int xo) {return val*(1<<p)+xo;}
void dijk() {
    int i, j;
    for (i=0;i<(n+1)*(m+1);i++) {
        for (j=0;j<(1<<p);j++) dis[rval(i,j)] = INF;
    }
    dis[rval(val(0,0),0)] = 0;
    priority_queue<pli> pq;
    pq.push(pli(0,rval(val(0,0),0)));
    while(!pq.empty()) {
        pli tmp = pq.top();
        pq.pop();
        int here = tmp.second;
        ll w = -tmp.first;
        for (i=0;i<lis[here].size();i++) {
            int there = lis[here][i].j;
            int ww = lis[here][i].w;
            if (dis[there]>dis[here]+ww) {
                dis[there]=dis[here]+ww;
                pq.push(pli(-dis[there],there));
            }
        }
    }
    printf("%lld\n",dis[rval(val(0,0),(1<<p)-1)]);
}
int main() {
    int i, j, k;
    //freopen("input","r",stdin);
    scanf("%d%d",&n,&m);
    if (n>40||m>40) return 0;
    for (i=0;i<n;i++) {
        for (j=0;j<m;j++) {
            scanf("%d",&arr[i][j]);
            arr[i][j]--;
        }
    }
    for (i=0;i<n;i++) {
        for (j=0;j<m;j++) {
            if (arr[i][j]>=0) arr[i][j] = p++;
        }
    }
    if (p>10) return 0;
    for (i=0;i<n;i++) {
        for (j=0;j<m+1;j++) {
            int a;
            scanf("%d",&a);
            for (k=0;k<(1<<p);k++) {
                lis[rval(val(i,j),k)].push_back(edge(rval(val(i+1,j),k),a,0));
                lis[rval(val(i+1,j),k)].push_back(edge(rval(val(i,j),k),a,0));
            }
        }
    }
    for (i=0;i<n+1;i++) {
        for (j=0;j<m;j++) {
            int a, x = 0;
            scanf("%d",&a);
            for (k=i;k<n;k++) {
                if (arr[k][j]>=0) x += (1<<arr[k][j]);
            }
            for (k=0;k<(1<<p);k++) {
                lis[rval(val(i,j),k)].push_back(edge(rval(val(i,j+1),k^x),a,x));
                lis[rval(val(i,j+1),k)].push_back(edge(rval(val(i,j),k^x),a,x));
            }
        }
    }
    dijk();
    return 0;
}

Compilation message (stderr)

wall.cpp: In constructor 'edge::edge(int, ll, int)':
wall.cpp:6:18: warning: 'edge::w' will be initialized after [-Wreorder]
    6 |     int j, x; ll w;
      |                  ^
wall.cpp:6:12: warning:   'int edge::x' [-Wreorder]
    6 |     int j, x; ll w;
      |            ^
wall.cpp:8:5: warning:   when initialized here [-Wreorder]
    8 |     edge(int j, ll w, int x):j(j),w(w),x(x){}
      |     ^~~~
wall.cpp: In function 'void dijk()':
wall.cpp:30:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |         for (i=0;i<lis[here].size();i++) {
      |                  ~^~~~~~~~~~~~~~~~~
wall.cpp:29:12: warning: unused variable 'w' [-Wunused-variable]
   29 |         ll w = -tmp.first;
      |            ^
wall.cpp: In function 'int main()':
wall.cpp:44:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |     scanf("%d%d",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~
wall.cpp:48:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |             scanf("%d",&arr[i][j]);
      |             ~~~~~^~~~~~~~~~~~~~~~~
wall.cpp:61:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |             scanf("%d",&a);
      |             ~~~~~^~~~~~~~~
wall.cpp:71:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |             scanf("%d",&a);
      |             ~~~~~^~~~~~~~~

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