oj.uz

Submission #676459

# Submission time Handle Problem Language Result Execution time Memory
676459 2022-12-31T03:07:03 Z vjudge1 Wall (CEOI14_wall) C++17
30 / 100
 1381 ms 199016 KB 
#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

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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 49736 KB Output is correct
2 Correct 25 ms 50260 KB Output is correct
3 Correct 24 ms 49964 KB Output is correct
4 Correct 25 ms 50256 KB Output is correct
5 Correct 24 ms 49748 KB Output is correct
6 Correct 25 ms 50260 KB Output is correct
7 Correct 737 ms 123352 KB Output is correct
8 Correct 41 ms 54988 KB Output is correct
9 Correct 25 ms 49876 KB Output is correct
10 Correct 28 ms 49996 KB Output is correct
11 Correct 1131 ms 152084 KB Output is correct
12 Correct 65 ms 57804 KB Output is correct
13 Correct 364 ms 125876 KB Output is correct
14 Correct 1381 ms 187892 KB Output is correct
15 Correct 30 ms 50132 KB Output is correct

Subtask #2
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 25 ms 49620 KB Output isn't correct
2 Incorrect 25 ms 49596 KB Output isn't correct
3 Incorrect 26 ms 49620 KB Output isn't correct
4 Correct 31 ms 50828 KB Output is correct
5 Incorrect 25 ms 49548 KB Output isn't correct
6 Incorrect 28 ms 49620 KB Output isn't correct
7 Incorrect 26 ms 49608 KB Output isn't correct
8 Incorrect 31 ms 49608 KB Output isn't correct
9 Correct 177 ms 85072 KB Output is correct
10 Correct 35 ms 52212 KB Output is correct
11 Incorrect 25 ms 49536 KB Output isn't correct
12 Incorrect 27 ms 49620 KB Output isn't correct
13 Incorrect 29 ms 49620 KB Output isn't correct
14 Correct 1344 ms 199016 KB Output is correct
15 Correct 181 ms 87012 KB Output is correct
16 Correct 31 ms 50872 KB Output is correct
17 Incorrect 25 ms 49636 KB Output isn't correct
18 Incorrect 26 ms 49620 KB Output isn't correct

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 25 ms 49620 KB Output isn't correct
2 Incorrect 26 ms 49632 KB Output isn't correct
3 Incorrect 25 ms 49660 KB Output isn't correct
4 Incorrect 25 ms 49588 KB Output isn't correct
5 Incorrect 26 ms 49620 KB Output isn't correct
6 Incorrect 26 ms 49656 KB Output isn't correct
7 Incorrect 27 ms 49564 KB Output isn't correct
8 Incorrect 26 ms 49620 KB Output isn't correct
9 Incorrect 29 ms 49604 KB Output isn't correct
10 Incorrect 31 ms 49612 KB Output isn't correct
11 Incorrect 26 ms 49568 KB Output isn't correct
12 Incorrect 26 ms 49624 KB Output isn't correct
13 Incorrect 26 ms 49548 KB Output isn't correct
14 Incorrect 26 ms 49628 KB Output isn't correct
15 Incorrect 26 ms 49660 KB Output isn't correct
16 Incorrect 26 ms 49636 KB Output isn't correct
17 Incorrect 30 ms 49564 KB Output isn't correct
18 Incorrect 26 ms 49620 KB Output isn't correct
19 Incorrect 27 ms 49568 KB Output isn't correct
20 Incorrect 25 ms 49616 KB Output isn't correct