Submission #29425

#TimeUsernameProblemLanguageResultExecution timeMemory
29425cdemirerSoccer (JOI17_soccer)C++14
5 / 100
3 ms8320 KiB
#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) { potcoords.pb(mp(a.first, b.second)); potcoords.pb(mp(b.first, a.second)); } } 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:129: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);
                                  ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...