# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
1030503 |
2024-07-22T06:08:54 Z |
browntoad |
Soccer (JOI17_soccer) |
C++14 |
|
508 ms |
123844 KB |
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
#define REP1(i, n) FOR(i, 1, n+1)
#define RREP(i, n) for (int i = (n)-1; i >= 0; i--)
#define RREP1(i, n) for (int i = (n); i >= 1; i--)
#define pii pair<int, int>
#define ppi pair<pii, int>
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) (int)((x).size())
#define f first
#define s second
#define pb push_back
#define endl '\n'
#define IOS() ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
const ll maxn = 505;
const ll mod = 1e9+7;
const ll inf = 1ll<<60;
ll mpw(ll a, ll p){
ll ret = 1;
while(p > 0){
if (p & 1){
ret *= a;
ret %= mod;
}
p >>= 1;
a *= a;
a %= mod;
}
return ret;
}
ll inv(ll a){
return mpw(a, mod-2);
}
int n, m, a, b, c;
vector<pii> g[3*maxn*maxn];
int hsh(ppi v){
return v.f.f + v.f.s*n + v.s*n*m;
}
ppi rvhsh(int v){
return {{v%n, (v/n)%m}, v/(n*m)};
}
vector<int> sp(3*maxn*maxn), occ(3*maxn*maxn);
int dij(int st, int en){
fill(ALL(sp), inf);
sp[st] = 0;
priority_queue<pii, vector<pii>, greater<pii> > pq;
pq.push({sp[st], st});
while(SZ(pq)){
pii tp = pq.top(); pq.pop();
if (occ[tp.s]) continue;
occ[tp.s] = 1;
for (auto y:g[tp.s]){
if (sp[y.f] > sp[tp.s] + y.s){
sp[y.f] = sp[tp.s] + y.s;
pq.push({sp[y.f], y.f});
}
}
}
return sp[en];
}
void add_edge(int ui, int uj, int uw, int vi, int vj, int vw, int cst, bool doubly){
int t1 = hsh({{ui, uj}, uw});
int t2 = hsh({{vi, vj}, vw});
g[t1].pb({t2, cst});
/*cout<<ui<<' '<<uj<<' '<<uw<<" -";
if (!doubly) cout<<">";
cout<<' '<<vi<<' '<<vj<<' '<<vw<<" with cost "<<cst<<endl;*/
if (doubly) g[t2].pb({t1, cst});
}
bool dd[maxn][maxn];
int dis[maxn][maxn]; // distance from nearest guy
vector<int> dx = {1, 0, -1, 0};
vector<int> dy = {0, 1, 0, -1};
signed main(){
IOS();
cin>>n>>m>>a>>b>>c;
n++; m++;
int t; cin>>t;
pii st, en;
cin>>st.f>>st.s;
dd[st.f][st.s] = 1;
REP(i, t-2){
pii inter; cin>>inter.f>>inter.s;
dd[inter.f][inter.s] = 1;
}
cin>>en.f>>en.s;
dd[en.f][en.s] = 1;
int t1, t2;
REP(i, n) REP(j, m) {
add_edge(i, j, 0, i, j, 1, b, 0);
add_edge(i, j, 0, i, j, 2, b, 0);
}
REP(i, n){
REP(j, m-1){
add_edge(i, j, 0, i, j+1, 0, c, 1);
add_edge(i, j, 1, i, j+1, 1, a, 1);
}
}
REP(i, n-1){
REP(j, m){
add_edge(i, j, 0, i+1, j, 0, c, 1);
add_edge(i, j, 2, i+1, j, 2, a, 1);
}
}
queue<pii> qu;
REP(i, n){
REP(j, m){
if (dd[i][j]) {
dis[i][j] = 0;
qu.push({i, j});
}
else dis[i][j] = inf;
}
}
while(SZ(qu)){
pii tp = qu.front(); qu.pop();
pii nw;
REP(i, 4){
nw = {tp.f + dx[i], tp.s + dy[i]};
if (nw.f >= 0 && nw.s >= 0 && nw.f < n && nw.s < m){
if (!dd[nw.f][nw.s]){
dd[nw.f][nw.s] = 1;
dis[nw.f][nw.s] = dis[tp.f][tp.s]+c;
qu.push({nw.f, nw.s});
}
}
}
}
REP(i, n){
REP(j, m){
add_edge(i, j, 1, i, j, 0, dis[i][j], 0);
add_edge(i, j, 2, i, j, 0, dis[i][j], 0);
}
}
int ret = dij(hsh({st, 0}), hsh({en, 0}));
cout<<ret<<endl;
}
// 42 gg
Compilation message
soccer.cpp: In function 'int main()':
soccer.cpp:104:9: warning: unused variable 't1' [-Wunused-variable]
104 | int t1, t2;
| ^~
soccer.cpp:104:13: warning: unused variable 't2' [-Wunused-variable]
104 | int t1, t2;
| ^~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
98 ms |
53500 KB |
Output is correct |
2 |
Correct |
12 ms |
30296 KB |
Output is correct |
3 |
Correct |
443 ms |
123028 KB |
Output is correct |
4 |
Correct |
445 ms |
123136 KB |
Output is correct |
5 |
Correct |
107 ms |
63572 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
424 ms |
123008 KB |
Output is correct |
2 |
Correct |
410 ms |
122992 KB |
Output is correct |
3 |
Correct |
320 ms |
105276 KB |
Output is correct |
4 |
Correct |
332 ms |
123076 KB |
Output is correct |
5 |
Correct |
306 ms |
105672 KB |
Output is correct |
6 |
Correct |
355 ms |
123072 KB |
Output is correct |
7 |
Correct |
434 ms |
122972 KB |
Output is correct |
8 |
Correct |
417 ms |
122920 KB |
Output is correct |
9 |
Correct |
458 ms |
122992 KB |
Output is correct |
10 |
Correct |
62 ms |
47572 KB |
Output is correct |
11 |
Correct |
430 ms |
123144 KB |
Output is correct |
12 |
Correct |
424 ms |
123076 KB |
Output is correct |
13 |
Correct |
292 ms |
105264 KB |
Output is correct |
14 |
Correct |
419 ms |
123072 KB |
Output is correct |
15 |
Correct |
334 ms |
105892 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
98 ms |
53500 KB |
Output is correct |
2 |
Correct |
12 ms |
30296 KB |
Output is correct |
3 |
Correct |
443 ms |
123028 KB |
Output is correct |
4 |
Correct |
445 ms |
123136 KB |
Output is correct |
5 |
Correct |
107 ms |
63572 KB |
Output is correct |
6 |
Correct |
424 ms |
123008 KB |
Output is correct |
7 |
Correct |
410 ms |
122992 KB |
Output is correct |
8 |
Correct |
320 ms |
105276 KB |
Output is correct |
9 |
Correct |
332 ms |
123076 KB |
Output is correct |
10 |
Correct |
306 ms |
105672 KB |
Output is correct |
11 |
Correct |
355 ms |
123072 KB |
Output is correct |
12 |
Correct |
434 ms |
122972 KB |
Output is correct |
13 |
Correct |
417 ms |
122920 KB |
Output is correct |
14 |
Correct |
458 ms |
122992 KB |
Output is correct |
15 |
Correct |
62 ms |
47572 KB |
Output is correct |
16 |
Correct |
430 ms |
123144 KB |
Output is correct |
17 |
Correct |
424 ms |
123076 KB |
Output is correct |
18 |
Correct |
292 ms |
105264 KB |
Output is correct |
19 |
Correct |
419 ms |
123072 KB |
Output is correct |
20 |
Correct |
334 ms |
105892 KB |
Output is correct |
21 |
Correct |
121 ms |
62980 KB |
Output is correct |
22 |
Correct |
502 ms |
123100 KB |
Output is correct |
23 |
Correct |
416 ms |
112136 KB |
Output is correct |
24 |
Correct |
491 ms |
121220 KB |
Output is correct |
25 |
Correct |
473 ms |
123076 KB |
Output is correct |
26 |
Correct |
465 ms |
123220 KB |
Output is correct |
27 |
Correct |
370 ms |
119632 KB |
Output is correct |
28 |
Correct |
401 ms |
119644 KB |
Output is correct |
29 |
Correct |
459 ms |
121820 KB |
Output is correct |
30 |
Correct |
389 ms |
119744 KB |
Output is correct |
31 |
Correct |
471 ms |
123104 KB |
Output is correct |
32 |
Correct |
483 ms |
123844 KB |
Output is correct |
33 |
Correct |
452 ms |
123076 KB |
Output is correct |
34 |
Correct |
508 ms |
123076 KB |
Output is correct |
35 |
Correct |
343 ms |
119544 KB |
Output is correct |