| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 25965 |
2017-06-25T08:55:10 Z |
시제연(#1089) |
Wall (CEOI14_wall) |
C++ |
|
1939 ms |
203708 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,int> pli;
struct edge {
int j; ll w;
edge(){}
edge(int j, ll w):j(j),w(w){}
};
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();
ll w = -tmp.first;
if (dis[tmp.second]!=w) continue;
for (i=0;i<lis[tmp.second].size();i++) {
int there = lis[tmp.second][i].j;
if (dis[there]>dis[tmp.second]+lis[tmp.second][i].w) {
dis[there]=dis[tmp.second]+lis[tmp.second][i].w;
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));
lis[rval(val(i+1,j),k)].push_back(edge(rval(val(i,j),k),a));
}
}
}
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));
lis[rval(val(i,j+1),k)].push_back(edge(rval(val(i,j),k^x),a));
}
}
}
dijk();
return 0;
}
Compilation message
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[tmp.second].size();i++) {
^
wall.cpp: In function 'int main()':
wall.cpp:52: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:56: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:69:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&a);
^
wall.cpp:79:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&a);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
67788 KB |
Output is correct |
| 2 |
Correct |
9 ms |
68344 KB |
Output is correct |
| 3 |
Correct |
16 ms |
68064 KB |
Output is correct |
| 4 |
Correct |
9 ms |
68184 KB |
Output is correct |
| 5 |
Correct |
16 ms |
67788 KB |
Output is correct |
| 6 |
Correct |
19 ms |
68184 KB |
Output is correct |
| 7 |
Correct |
1036 ms |
135676 KB |
Output is correct |
| 8 |
Correct |
36 ms |
72552 KB |
Output is correct |
| 9 |
Correct |
9 ms |
67920 KB |
Output is correct |
| 10 |
Correct |
16 ms |
68080 KB |
Output is correct |
| 11 |
Correct |
1656 ms |
163084 KB |
Output is correct |
| 12 |
Correct |
79 ms |
75208 KB |
Output is correct |
| 13 |
Correct |
546 ms |
138052 KB |
Output is correct |
| 14 |
Correct |
1939 ms |
195508 KB |
Output is correct |
| 15 |
Correct |
16 ms |
68248 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
67656 KB |
Output isn't correct |
| 2 |
Incorrect |
19 ms |
67656 KB |
Output isn't correct |
| 3 |
Incorrect |
16 ms |
67656 KB |
Output isn't correct |
| 4 |
Correct |
23 ms |
68712 KB |
Output is correct |
| 5 |
Incorrect |
23 ms |
67656 KB |
Output isn't correct |
| 6 |
Incorrect |
6 ms |
67656 KB |
Output isn't correct |
| 7 |
Incorrect |
6 ms |
67656 KB |
Output isn't correct |
| 8 |
Incorrect |
13 ms |
67656 KB |
Output isn't correct |
| 9 |
Correct |
226 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 |
16 ms |
67656 KB |
Output isn't correct |
| 13 |
Incorrect |
23 ms |
67656 KB |
Output isn't correct |
| 14 |
Correct |
1933 ms |
203708 KB |
Output is correct |
| 15 |
Correct |
266 ms |
102812 KB |
Output is correct |
| 16 |
Correct |
23 ms |
68872 KB |
Output is correct |
| 17 |
Incorrect |
13 ms |
67656 KB |
Output isn't correct |
| 18 |
Incorrect |
16 ms |
67656 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
67656 KB |
Output isn't correct |
| 2 |
Incorrect |
13 ms |
67656 KB |
Output isn't correct |
| 3 |
Incorrect |
13 ms |
67656 KB |
Output isn't correct |
| 4 |
Incorrect |
9 ms |
67656 KB |
Output isn't correct |
| 5 |
Incorrect |
6 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 |
Incorrect |
6 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 |
9 ms |
67656 KB |
Output isn't correct |
| 13 |
Incorrect |
6 ms |
67656 KB |
Output isn't correct |
| 14 |
Incorrect |
9 ms |
67656 KB |
Output isn't correct |
| 15 |
Incorrect |
6 ms |
67656 KB |
Output isn't correct |
| 16 |
Incorrect |
23 ms |
67656 KB |
Output isn't correct |
| 17 |
Incorrect |
19 ms |
67656 KB |
Output isn't correct |
| 18 |
Incorrect |
13 ms |
67656 KB |
Output isn't correct |
| 19 |
Incorrect |
6 ms |
67656 KB |
Output isn't correct |
| 20 |
Incorrect |
9 ms |
67656 KB |
Output isn't correct |
