| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 590361 |
2022-07-05T21:28:53 Z |
Gilwall |
Soccer (JOI17_soccer) |
C++14 |
|
263 ms |
262144 KB |
#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define all(v) v.begin(), v.end()
#define sz(v) (int)v.size()
#define sq(a) ((a)*(a))
#define MOO(i,a,b) for (int i=a; i<b; i++)
#define M00(i,a) for (int i=0; i<a; i++)
#define MOOd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define M00d(i,a) for (int i = (a)-1; i >= 0; i--)
#define per(i,a,b) for (int i = (b)-1; i >= a; i--)
#define rep(i,a,b) for (int i=a; i<b; i++)
#define FOR(i,a,b) for (int i=a; i<b; i++)
#define F0R(i,a) for (int i=0; i<a; i++)
#define ROF(i,a,b) for (int i = (b)-1; i >= a; i--)
#define R0F(i,a) for (int i = (a)-1; i >= 0; i--)
#define FAST ios::sync_with_stdio(0); cin.tie(0);
#define finish(x) return cout << x << endl, 0;
#define dbg(x) cerr << ">>> " << #x << " = " << x << endl;
#define _<< " _ " <<
#define int long long
typedef long double ld;
typedef pair<int,int> pi;
typedef pair<ld,ld> pd;
typedef complex<ld> cd;
typedef vector<int> vi;
typedef vector<ld> vld;
typedef vector<vector<int>> vvi;
const ld PI = acos(-1.0);
const ld EPS = 1e-7;
const int MOD = 1e9+7;
int POW(int b, int e) {
int r = 1;
while(e) {
if(e % 2 == 1) {
r *= b;
r %= MOD;
}
e /= 2;
b *= b;
b %= MOD;
}
return r;
}
int gcd(int a, int b) {
if(b > a) return gcd(b,a);
if(b == 0) return a;
return gcd(b, a % b);
}
int INV(int a) {
return POW(a, MOD-2);
}
//Constants and Variables here
int H, W;
int A,B,C;
int N;
template<int SZ> struct dijkstra {
const int inf = 1e15;
vector<pi> adj[SZ];
bool vis[SZ];
int d[SZ];
void addEdge(int u, int v, int l) {
adj[u].pb(mp(v, l));
}
int dist(int v) {
return d[v];
}
void build(int u) {
priority_queue<pi, vector<pi>, greater<pi>> pq;
M00(i, SZ) d[i] = inf;
d[u] = 0;
pq.push(mp(0, u));
while(!pq.empty()) {
pi t = pq.top(); pq.pop();
if(vis[t.s]) continue;
vis[t.s] = 1;
for(auto v: adj[t.s]) {
if(d[v.f] > d[t.s] + v.s) {
d[v.f] = d[t.s] + v.s;
pq.push(mp(d[t.s]+v.s, v.f));
}
}
}
}
};
const int V = 501*501;
vi dx = {0,0,1,-1};
vi dy = {1,-1,0,0};
int32_t main() { FAST
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
cin >> H >> W >> A >> B >> C >> N;
H++; W++;
vector<vi> arr(H, vi(W, -1));
queue<pair<pi, int>> Q;
vector<pi> players;
M00(i, N) {
int x, y;
cin >> x >> y;
players.pb(mp(x,y));
if(arr[x][y] < 0) {
arr[x][y] = 0;
Q.push(mp(mp(x,y),0));
}
}
while(Q.size() > 0) {
auto A = Q.front();
Q.pop();
int x = A.f.f, y = A.f.s;
int d = A.s;
M00(i, 4) {
int xx = x + dx[i], yy = y + dy[i];
if(0 <= xx && xx < H && 0 <= yy && yy <= W && arr[xx][yy] < 0) {
arr[xx][yy] = d + 1;
Q.push(mp(mp(xx,yy),d+1));
}
}
}
dijkstra<V> G;
M00(x, H) M00(y, W) {
//hash (x,y) -> x * W + y
int v = x*W + y;
M00(k, H) {
int w = k*W + y;
if(w != v) {
int cost = min(abs(k-x) * C, A * abs(k-x) + B + C*arr[k][y]);
G.addEdge(v, w, cost);
}
}
M00(k, W) {
int w = x*W + k;
if(w != v) {
int cost = min(abs(k-y) * C, A * abs(k-y) + B + C*arr[x][k]);
G.addEdge(v, w, cost);
}
}
}
int s = players[0].f * W + players[0].s;
int t = players[N-1].f * W + players[N-1].s;
G.build(s);
cout << G.dist(t) << endl;
}
Compilation message
soccer.cpp:29:9: warning: ISO C++11 requires whitespace after the macro name
29 | #define _<< " _ " <<
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
263 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
263 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
263 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
