oj.uz

Submission #25964

# Submission time Handle Problem Language Result Execution time Memory
25964 2017-06-25T08:50:56 Z 시제연(#1089) Wall (CEOI14_wall) C++
20 / 100
 2000 ms 203708 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:9:18: warning: 'edge::w' will be initialized after [-Wreorder]
     int j, x; ll w;
                  ^
wall.cpp:9:12: warning:   'int edge::x' [-Wreorder]
     int j, x; ll w;
            ^
wall.cpp:11:5: warning:   when initialized here [-Wreorder]
     edge(int j, ll w, int x):j(j),w(w),x(x){}
     ^
wall.cpp: In function 'void dijk()':
wall.cpp:36:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (i=0;i<lis[here].size();i++) {
                   ^
wall.cpp:35:12: warning: unused variable 'w' [-Wunused-variable]
         ll w = -tmp.first;
            ^
wall.cpp: In function 'int main()':
wall.cpp:53:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&n,&m);
                        ^
wall.cpp:57:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d",&arr[i][j]);
                                   ^
wall.cpp:70:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d",&a);
                           ^
wall.cpp:80:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d",&a);
                           ^

Subtask #1
20.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 67788 KB Output is correct
2 Correct 23 ms 68344 KB Output is correct
3 Correct 19 ms 68064 KB Output is correct
4 Correct 16 ms 68184 KB Output is correct
5 Correct 19 ms 67788 KB Output is correct
6 Correct 23 ms 68184 KB Output is correct
7 Correct 1246 ms 135676 KB Output is correct
8 Correct 39 ms 72552 KB Output is correct
9 Correct 19 ms 67920 KB Output is correct
10 Correct 23 ms 68080 KB Output is correct
11 Correct 1776 ms 163084 KB Output is correct
12 Correct 96 ms 75208 KB Output is correct
13 Correct 533 ms 138052 KB Output is correct
14 Execution timed out 2000 ms 195508 KB Execution timed out
15 Correct 16 ms 68248 KB Output is correct

Subtask #2
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 67656 KB Output isn't correct
2 Incorrect 23 ms 67656 KB Output isn't correct
3 Incorrect 9 ms 67656 KB Output isn't correct
4 Correct 16 ms 68712 KB Output is correct
5 Incorrect 13 ms 67656 KB Output isn't correct
6 Incorrect 13 ms 67656 KB Output isn't correct
7 Incorrect 9 ms 67656 KB Output isn't correct
8 Incorrect 16 ms 67656 KB Output isn't correct
9 Correct 239 ms 100484 KB Output is correct
10 Correct 29 ms 70060 KB Output is correct
11 Incorrect 13 ms 67656 KB Output isn't correct
12 Incorrect 6 ms 67656 KB Output isn't correct
13 Incorrect 13 ms 67656 KB Output isn't correct
14 Execution timed out 2000 ms 203708 KB Execution timed out
15 Correct 259 ms 102812 KB Output is correct
16 Correct 19 ms 68872 KB Output is correct
17 Incorrect 16 ms 67656 KB Output isn't correct
18 Incorrect 16 ms 67656 KB Output isn't correct

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 67656 KB Output isn't correct
2 Incorrect 16 ms 67656 KB Output isn't correct
3 Incorrect 9 ms 67656 KB Output isn't correct
4 Incorrect 13 ms 67656 KB Output isn't correct
5 Incorrect 6 ms 67656 KB Output isn't correct
6 Incorrect 9 ms 67656 KB Output isn't correct
7 Incorrect 13 ms 67656 KB Output isn't correct
8 Incorrect 13 ms 67656 KB Output isn't correct
9 Incorrect 9 ms 67656 KB Output isn't correct
10 Incorrect 16 ms 67656 KB Output isn't correct
11 Incorrect 9 ms 67656 KB Output isn't correct
12 Incorrect 13 ms 67656 KB Output isn't correct
13 Incorrect 9 ms 67656 KB Output isn't correct
14 Incorrect 9 ms 67656 KB Output isn't correct
15 Incorrect 19 ms 67656 KB Output isn't correct
16 Incorrect 6 ms 67656 KB Output isn't correct
17 Incorrect 16 ms 67656 KB Output isn't correct
18 Incorrect 13 ms 67656 KB Output isn't correct
19 Incorrect 9 ms 67656 KB Output isn't correct
20 Incorrect 16 ms 67656 KB Output isn't correct