Submission #1163621

---

Source Code Expand

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <functional>
#include <cmath>
#include <complex>
#include <cctype>
#include <cassert>
#include <sstream>
#include <ctime>
 
using namespace std;
 
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()
 
template<typename A, typename B> inline bool chmax(A &a, B b) { if (a<b) { a=b; return 1; } return 0; }
template<typename A, typename B> inline bool chmin(A &a, B b) { if (a>b) { a=b; return 1; } return 0; }
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<int, pii> P;
typedef vector<pii> vp;

#define INF (1<<29)
#define INFL (1ll<<60)
#define EPS (1e-8)
#define PI (acos(-1))
const ll MOD = 1000000007ll;

int W, H, Q;
vector<pii> B[2]; // tate, yoko

void insert(set<pii> &s, int x) {
	if (s.empty()) return;
	
	set<pii>::iterator it = s.lower_bound(pii(x, x));
	if (it == s.end() || it->first > x) it--;
	
	pii n1 = *it, n2 = *it;
	n1.second = x - 1; n2.first = x + 1;
	
	s.erase(*it);
	
	if (n1.second >= n1.first) s.insert(n1);
	if (n2.second >= n2.first) s.insert(n2);
}

int nextfind(set<pii> &s, int x, bool rev) {
	set<pii>::iterator it = s.lower_bound(pii(x, x));
	
	int res = INF;
	if (rev) res = -INF;
	
	if (it == s.end() || rev) it--;
	
	if (!rev) {
		if (it->first <= x && it->second >= x) chmin(res, x);
		
		if (it->first >= x) chmin(res, it->first);
		
		if (it != s.begin()) {
			it--;
			if (it->second >= x) chmin(res, it->second);
		}
	}
	else {
		if (it->first <= x && it->second >= x) res = x;
		else if (it->second <= x) chmax(res, it->second);
	}
	
	return res;
}

void update(map<int, ll> &m, int pos, ll x) {
	if (m.find(pos) == m.end()) m[pos] = x;
	else chmin(m[pos], x);
}


int main() {
	cin >> W >> H >> Q;
	
	REP(i, Q) {
		int t, d, x;
		scanf("%d %d %d", &t, &d, &x);
		B[d].push_back(pii(t, x));
	}
	
	assert(W <= 100);
	assert(H <= 100);
	
	ll ans = INFL;
	bool ng = false;
	
	FOR(x, 1, W + 1) FOR(y, 1, H + 1) {
		
		ll sum = 0;
		
		REP(i, 2) {
			priority_queue<pii, vector<pii>, greater<pii> > pq;
			REP(j, B[i].size()) pq.push(B[i][j]);
			
			vector<set<pii> > vs;
			while (!pq.empty()) {
				set<pii> s;
				if (i == 0) s.insert(pii(1, W));
				else s.insert(pii(1, H));
				
				int nt = pq.top().first;
				
				while (!pq.empty()) {
					pii now = pq.top();
					if (now.first != nt) break;
					pq.pop();
					
					insert(s, now.second);
				}
				
				if (s.size() == 0) {
					ng = true;
					break;
				}
				
				vs.push_back(s);
			}
			
			if (ng) break;
			
			map<int, ll> pos;
			if (i == 0) pos[x] = 0;
			else pos[y] = 0;
			
			REP(j, vs.size()) {
				map<int, ll> nextpos;
				
				for (map<int, ll>::iterator it = pos.begin(); it != pos.end(); it++) {
					int now = it->first;
					int ncost = it->second;
					
					int next = nextfind(vs[j], now, false);
					
					if (next != INF) update(nextpos, next, ncost + abs(next - now));
					if (next == it->first) continue;
					
					next = nextfind(vs[j], now, true);
					if (next != -INF) update(nextpos, next, ncost + abs(next - now));
				}
				
				pos = nextpos;
			}
			
			ll now = INFL;
			for (map<int, ll>::iterator it = pos.begin(); it != pos.end(); it++)
				chmin(now, it->second);
			sum += now;
		}
		
		chmin(ans, sum);
	}
	
	if (ng) puts("-1");
	else cout << ans << endl;
	
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:93:32: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d", &t, &d, &x);
                                ^

Judge Result