Submission #29428

#	Time	Username	Problem	Language	Result	Execution time	Memory
29428		cdemirer	Soccer (JOI17_soccer)	C++14	5 / 100	3 ms	8188 KiB

soccer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> llp;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef vector<pair<int, int> > vii;
typedef vector<vector<pair<int, int> > > vvii;
#define pb(x) push_back(x)
#define mp(x, y) make_pair(x, y)

int N;
int H, W;
ll A, B, C;
set<ii> sVer[501];
set<ii> sHor[501];
ii coord[200000];
bool dolu[501][501] = {0};
vvi edges;
ll dists[200000];
int parent[200000];

void determineEdges(int x) {
	int xs = coord[x].first, xt = coord[x].second;
	set<ii>::iterator it = sHor[xs].find(mp(xt, x));
	set<ii>::iterator it_ = it;
	int llim = 0; if (it != sHor[xs].begin()) {it--; llim = (*it).first+1; edges[x].pb((*it).second); }
	it = it_;
	int rlim = W+1; 
	if (it != sHor[xs].end()) it++;
	if (it != sHor[xs].end()) {
		rlim = (*it).first; edges[x].pb((*it).second);
	}
	for (int i = llim; i < rlim; i++) {
		set<ii>::iterator it2 = sVer[i].upper_bound(mp(xs, 1000000000));
		if (it2 != sVer[i].end()) { edges[x].pb((*it2).second); }
		if (it2 != sVer[i].begin()) it2--;
		else continue;
		if (i == xt) {
			if (it2 != sVer[i].begin()) {
				it2--;
				edges[x].pb((*it2).second);
			}
		}
		else {
			edges[x].pb((*it2).second);
		}
	}
}

ll elens[501][501];
ll edgelen(int dx, int dy) {
	if (elens[dx][dy] != -1) return elens[dx][dy];
	ll dogrultuC1 = min(dx, dy) * C;
	ll duzyol1 = max(dx, dy);
	ll duzyolC1 = C * duzyol1;
	duzyolC1 = min(duzyolC1, A*duzyol1+B);
	ll dogrultuC2 = max(dx, dy) * C;
	ll duzyol2 = min(dx, dy);
	ll duzyolC2 = C * duzyol2;
	duzyolC2 = min(duzyolC2, A*duzyol2+B);
	ll ans = min(dogrultuC1 + duzyolC1, dogrultuC2 + duzyolC2);
	elens[dx][dy] = ans;
	return ans;
}

ll getBestLen(const vii &cs, ii b) {
	ll best = (ll)1e18;
	for (int i = 0; i < cs.size(); i++) {
		best = min(best, edgelen(abs(cs[i].first-b.first), abs(cs[i].second-b.second)));
	}
	return best;
}

int main(int argc, char **argv) {

	memset(elens, -1, sizeof(elens));

	//freopen("input", "r", stdin);
	//freopen("output", "w", stdout);

	scanf("%d%d", &H, &W);
	scanf("%lld%lld%lld", &A, &B, &C);
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		int s, t; scanf("%d%d", &s, &t);
		if (dolu[s][t]) {
			i--;
			N--;
			continue;
		}
		dolu[s][t] = true;
		coord[i] = mp(s, t);
		sVer[t].insert(mp(s, i));
		sHor[s].insert(mp(t, i));
	}
	edges.resize(N);
	for (int i = 0; i < N; i++) {
		determineEdges(i);
		/*for (int j = 0; j < edges[i].size(); j++) {
			cerr << edges[i][j].first << " ";
		} cerr << endl;*/
	}
	set<llp> S;
	dists[0] = 0;
	parent[0] = -1;
	S.insert(mp(dists[0], 0));
	for (int i = 1; i < N; i++) {
		dists[i] = (ll)1e18;
		S.insert(mp(dists[i], i));
	}
	while ( ! S.empty() ) {
		llp x = *S.begin();
		S.erase(S.begin());
		
		// find possible coords
		vii potcoords;
		potcoords.pb(coord[x.second]);
		if (parent[x.second] != -1) {
			ii a = coord[parent[x.second]];
			ii b = coord[x.second];
			if (a.first != b.first && a.second != b.second) {
				int dx = b.first - a.first;
				int dy = b.second - a.second;
				if (dx >= dy) {
					for (int k = 1; k <= dx; k++)
					potcoords.pb(mp(a.first+k, a.second));
				}
				if (dy >= dx) {
					for (int k = 1; k <= dy; k++)
					potcoords.pb(mp(a.first, a.second+k));
				}
			}
		}

		for (int i = 0; i < edges[x.second].size(); i++) {
			int v = edges[x.second][i];
			if (parent[x.second] == v) continue;

			//ll e = edges[x.second][i].second;
			ll e = getBestLen(potcoords, coord[v]);

			if (dists[x.second] + e < dists[v]) {
				S.erase(mp(dists[v], v));
				dists[v] = dists[x.second] + e;
				S.insert(mp(dists[v], v));
				parent[v] = x.second;
			}
		}
	}
	ll ans = dists[N-1];
	printf("%lld\n", ans);

	return 0;
}

Compilation message (stderr)

soccer.cpp: In function 'll getBestLen(const vii&, ii)':
soccer.cpp:70:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < cs.size(); i++) {
                    ^
soccer.cpp: In function 'int main(int, char**)':
soccer.cpp:137:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < edges[x.second].size(); i++) {
                     ^
soccer.cpp:83:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &H, &W);
                       ^
soccer.cpp:84:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld%lld%lld", &A, &B, &C);
                                   ^
soccer.cpp:85:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
                 ^
soccer.cpp:87:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int s, t; scanf("%d%d", &s, &t);
                                  ^

• Subtask 1: 5 / 5
• Subtask 2: 0 / 30
• Subtask 3: 0 / 65