Submission #101164

#	Time	Username	Problem	Language	Result	Execution time	Memory
101164		square1001	Wall (CEOI14_wall)	C++14	30 / 100	926 ms	17152 KiB

wall

#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 (stderr)

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 / 30
• Subtask 2: 0 / 30
• Subtask 3: 0 / 40