| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 29447 |
2017-07-19T11:28:53 Z |
cdemirer |
Soccer (JOI17_soccer) |
C++14 |
|
3 ms |
9880 KB |
#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];
ii parentpos[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;
}
llp getBestLen(const vii &cs, ii b) {
ll best = (ll)1e18;
ll besti = 0;
for (int i = 0; i < cs.size(); i++) {
if (edgelen(abs(cs[i].first-b.first), abs(cs[i].second-b.second)) <= best) {
besti = i;
best = edgelen(abs(cs[i].first-b.first), abs(cs[i].second-b.second));
}
}
return mp(best, besti);
}
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 = parentpos[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 (abs(dx) >= abs(dy)) {
for (int k = 0; k < dy; k++)
potcoords.pb(mp(a.first+dx, a.second+k));
for (int k = 0; k > dy; k--)
potcoords.pb(mp(a.first+dx, a.second+k));
}
if (abs(dy) >= abs(dx)) {
for (int k = 0; k < dx; k++)
potcoords.pb(mp(a.first+k, a.second+dy));
for (int k = 0; k > dx; k--)
potcoords.pb(mp(a.first+k, a.second+dy));
}
}
}
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;
llp ee = getBestLen(potcoords, coord[v]);
ll e = ee.first;
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;
parentpos[v] = potcoords[ee.second];
}
}
}
ll ans = dists[N-1];
printf("%lld\n", ans);
return 0;
}
Compilation message
soccer.cpp: In function 'llp getBestLen(const vii&, ii)':
soccer.cpp:72: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:146:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < edges[x.second].size(); i++) {
^
soccer.cpp:88: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:89: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:90:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &N);
^
soccer.cpp:92: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 time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
9748 KB |
Output is correct |
| 2 |
Correct |
0 ms |
9748 KB |
Output is correct |
| 3 |
Correct |
0 ms |
9748 KB |
Output is correct |
| 4 |
Correct |
0 ms |
9748 KB |
Output is correct |
| 5 |
Correct |
0 ms |
9748 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
9748 KB |
Output is correct |
| 2 |
Correct |
0 ms |
9880 KB |
Output is correct |
| 3 |
Correct |
0 ms |
9880 KB |
Output is correct |
| 4 |
Incorrect |
3 ms |
9880 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
9748 KB |
Output is correct |
| 2 |
Correct |
0 ms |
9748 KB |
Output is correct |
| 3 |
Correct |
0 ms |
9748 KB |
Output is correct |
| 4 |
Correct |
0 ms |
9748 KB |
Output is correct |
| 5 |
Correct |
0 ms |
9748 KB |
Output is correct |
| 6 |
Correct |
0 ms |
9748 KB |
Output is correct |
| 7 |
Correct |
0 ms |
9880 KB |
Output is correct |
| 8 |
Correct |
0 ms |
9880 KB |
Output is correct |
| 9 |
Incorrect |
3 ms |
9880 KB |
Output isn't correct |
| 10 |
Halted |
0 ms |
0 KB |
- |
