oj.uz

Submission #101164

# Submission time Handle Problem Language Result Execution time Memory
101164 2019-03-17T07:23:36 Z square1001 Wall (CEOI14_wall) C++14
30 / 100
 926 ms 17152 KB 
#include <queue>
#include <vector>
#include <cassert>
#include <iostream>
#include <functional>
using namespace std;
const long long inf = 1LL << 61;
class edge {
public:
	int to, bit; long long cost;
	edge() : to(-1), cost(0), bit(0) {};
	edge(int to_, long long cost_, int bit_) : to(to_), cost(cost_), bit(bit_) {};
};
class state {
public:
	int pos, bit; long long cost;
	state() : pos(-1), cost(0), bit(0) {};
	state(int pos_, long long cost_, int bit_) : pos(pos_), cost(cost_), bit(bit_) {};
	bool operator>(const state& s) const {
		return cost > s.cost;
	}
};
int main() {
	cin.tie(0);
	ios_base::sync_with_stdio(false);
	int H, W;
	cin >> H >> W;
	vector<vector<int> > A(H, vector<int>(W));
	vector<pair<int, int> > points;
	for (int i = 0; i < H; ++i) {
		for (int j = 0; j < W; ++j) {
			cin >> A[i][j];
			if (A[i][j] == 1) {
				points.push_back(make_pair(i, j));
			}
		}
	}
	assert(H <= 40 && W <= 40 && points.size() <= 10);
	vector<vector<edge> > G((H + 1) * (W + 1));
	for (int i = 0; i < H; ++i) {
		for (int j = 0; j <= W; ++j) {
			int x;
			cin >> x;
			int changebit = 0;
			for (int k = 0; k < points.size(); ++k) {
				if (points[k].first == i && points[k].second < j) {
					changebit ^= 1 << k;
				}
			}
			G[i * (W + 1) + j].push_back(edge((i + 1) * (W + 1) + j, x, changebit));
			G[(i + 1) * (W + 1) + j].push_back(edge(i * (W + 1) + j, x, changebit));
		}
	}
	for (int i = 0; i <= H; ++i) {
		for (int j = 0; j < W; ++j) {
			int x;
			cin >> x;
			G[i * (W + 1) + j].push_back(edge(i * (W + 1) + j + 1, x, 0));
			G[i * (W + 1) + j + 1].push_back(edge(i * (W + 1) + j, x, 0));
		}
	}
	vector<vector<long long> > dist((H + 1) * (W + 1), vector<long long>(1 << points.size(), inf));
	priority_queue<state, vector<state>, greater<state> > que;
	que.push(state(0, 0, 0));
	dist[0][0] = 0;
	while (!que.empty()) {
		state u = que.top(); que.pop();
		for (edge e : G[u.pos]) {
			long long newd = dist[u.pos][u.bit] + e.cost;
			if (dist[e.to][u.bit ^ e.bit] > newd) {
				dist[e.to][u.bit ^ e.bit] = newd;
				que.push(state(e.to, dist[e.to][u.bit ^ e.bit], u.bit ^ e.bit));
			}
		}
	}
	long long ans = dist[0][(1 << points.size()) - 1];
	cout << ans << '\n';
	return 0;
}

Compilation message

wall.cpp: In constructor 'edge::edge()':
wall.cpp:10:25: warning: 'edge::cost' will be initialized after [-Wreorder]
  int to, bit; long long cost;
                         ^~~~
wall.cpp:10:10: warning:   'int edge::bit' [-Wreorder]
  int to, bit; long long cost;
          ^~~
wall.cpp:11:2: warning:   when initialized here [-Wreorder]
  edge() : to(-1), cost(0), bit(0) {};
  ^~~~
wall.cpp: In constructor 'edge::edge(int, long long int, int)':
wall.cpp:10:25: warning: 'edge::cost' will be initialized after [-Wreorder]
  int to, bit; long long cost;
                         ^~~~
wall.cpp:10:10: warning:   'int edge::bit' [-Wreorder]
  int to, bit; long long cost;
          ^~~
wall.cpp:12:2: warning:   when initialized here [-Wreorder]
  edge(int to_, long long cost_, int bit_) : to(to_), cost(cost_), bit(bit_) {};
  ^~~~
wall.cpp: In constructor 'state::state()':
wall.cpp:16:26: warning: 'state::cost' will be initialized after [-Wreorder]
  int pos, bit; long long cost;
                          ^~~~
wall.cpp:16:11: warning:   'int state::bit' [-Wreorder]
  int pos, bit; long long cost;
           ^~~
wall.cpp:17:2: warning:   when initialized here [-Wreorder]
  state() : pos(-1), cost(0), bit(0) {};
  ^~~~~
wall.cpp: In constructor 'state::state(int, long long int, int)':
wall.cpp:16:26: warning: 'state::cost' will be initialized after [-Wreorder]
  int pos, bit; long long cost;
                          ^~~~
wall.cpp:16:11: warning:   'int state::bit' [-Wreorder]
  int pos, bit; long long cost;
           ^~~
wall.cpp:18:2: warning:   when initialized here [-Wreorder]
  state(int pos_, long long cost_, int bit_) : pos(pos_), cost(cost_), bit(bit_) {};
  ^~~~~
wall.cpp: In function 'int main()':
wall.cpp:45:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int k = 0; k < points.size(); ++k) {
                    ~~^~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 3 ms 512 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 4 ms 512 KB Output is correct
7 Correct 421 ms 9196 KB Output is correct
8 Correct 12 ms 1152 KB Output is correct
9 Correct 3 ms 556 KB Output is correct
10 Correct 4 ms 512 KB Output is correct
11 Correct 802 ms 13696 KB Output is correct
12 Correct 30 ms 1408 KB Output is correct
13 Correct 252 ms 9588 KB Output is correct
14 Correct 926 ms 17152 KB Output is correct
15 Correct 4 ms 640 KB Output is correct

Subtask #2
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 3 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 3 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Correct 7 ms 768 KB Output is correct
5 Runtime error 4 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 3 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 4 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 3 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Correct 91 ms 4848 KB Output is correct
10 Correct 9 ms 1024 KB Output is correct
11 Runtime error 3 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 3 ms 556 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 4 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Correct 907 ms 15356 KB Output is correct
15 Correct 100 ms 6008 KB Output is correct
16 Correct 7 ms 768 KB Output is correct
17 Runtime error 17 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 4 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 9 ms 1152 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 7 ms 1152 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 9 ms 1152 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 7 ms 1024 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 10 ms 2304 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 8 ms 1152 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 12 ms 1664 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 11 ms 1712 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 10 ms 1664 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 11 ms 1664 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 11 ms 1664 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 8 ms 1152 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 13 ms 1664 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 14 ms 2432 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 18 ms 2432 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 15 ms 2304 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 13 ms 2432 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 21 ms 2304 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 13 ms 2304 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 14 ms 2432 KB Execution killed with signal 11 (could be triggered by violating memory limits)