Submission #575866

#TimeUsernameProblemLanguageResultExecution timeMemory
575866vaavenSoccer (JOI17_soccer)C++14
100 / 100
424 ms23112 KiB
#pragma GCC target("avx2") #pragma GCC optimize("O3") #include <iostream> #include <vector> #include <algorithm> #include <math.h> #include <set> #include <stack> #include <iomanip> #include <bitset> #include <map> #include <cassert> #include <array> #include <queue> #include <cstring> #include <random> #include <unordered_set> #include <unordered_map> #define pqueue priority_queue #define pb(x) push_back(x) #define endl '\n' #define all(x) x.begin(), x.end() #define int long long using namespace std; typedef long long ll; typedef unsigned long long ull; typedef long double ld; typedef vector<int> vi; typedef vector<vector<int> > vvi; // typedef tuple<ll, ll, ll> tiii; typedef pair<int, int> pii; typedef vector<pair<int, int> > vpii; typedef vector<bool> vb; typedef vector<string> vs; typedef vector<char> vc; const int inf = 1e9 + 228; const int infll = 1e18; const ll mod = 1e9 + 7; const ll mod2 = 998244353; const ld eps = 1e-14; void fast_io(){ ios_base::sync_with_stdio(0); cin.tie(0); // freopen("inputik.txt", "r", stdin); // freopen("outputik.txt", "w", stdout); } int w, h, n, a, b, c; pii kek[100000]; int dist1[501][501]; int dist2[501][501][5]; int dx[4] = {0, 0, 1, -1}; int dy[4] = {1, -1, 0, 0}; bool check(pii i){ return 0 <= i.first && i.first <= w && 0 <= i.second && i.second <= h; } void calc1(){ queue<pii> q; for(int i=0; i<n; i++){ dist1[kek[i].first][kek[i].second] = 0; q.push(kek[i]); } while(!q.empty()){ pii cur = q.front(); q.pop(); for(int j=0; j<4; j++){ pii nw = make_pair(cur.first + dx[j], cur.second + dy[j]); if(check(nw) && dist1[nw.first][nw.second] > dist1[cur.first][cur.second] + c){ dist1[nw.first][nw.second] = dist1[cur.first][cur.second] + c; q.push(nw); } } } } void calc2(){ pqueue<array<int, 4>> q; q.push({0, kek[0].first, kek[0].second, 4}); while(!q.empty()){ array<int, 4> cur = q.top(); q.pop(); // cout << cur[0] << " " << cur[1] << " " << cur[2] << " " << cur[3] << endl; if(cur[3] == 4){ for(int i=0; i<4; i++){ array<int, 4> nw = {cur[0] - b, cur[1], cur[2], i}; if(check({nw[1], nw[2]}) && dist2[nw[1]][nw[2]][nw[3]] > -nw[0]){ dist2[nw[1]][nw[2]][nw[3]] = -nw[0]; q.push(nw); } } for(int i=0; i<4; i++){ array<int, 4> nw = {cur[0] - c, cur[1] + dx[i], cur[2] + dy[i], 4}; if(check({nw[1], nw[2]}) && dist2[nw[1]][nw[2]][nw[3]] > -nw[0]){ dist2[nw[1]][nw[2]][nw[3]] = -nw[0]; q.push(nw); } } } else{ if(dist2[cur[1]][cur[2]][4] > -cur[0] + dist1[cur[1]][cur[2]]){ dist2[cur[1]][cur[2]][4] = min(dist2[cur[1]][cur[2]][4], -cur[0] + dist1[cur[1]][cur[2]]); q.push({cur[0] - dist1[cur[1]][cur[2]], cur[1], cur[2], 4}); } if(cur[1] == kek[n-1].first && cur[2] == kek[n-1].second && dist2[cur[1]][cur[2]][4] > -cur[0]){ dist2[cur[1]][cur[2]][4] = min(dist2[cur[1]][cur[2]][4], -cur[0]); q.push({cur[0], cur[1], cur[2], 4}); } array<int, 4> nw = {cur[0] - a, cur[1] + dx[cur[3]], cur[2] + dy[cur[3]], cur[3]}; if(check({nw[1], nw[2]}) && dist2[nw[1]][nw[2]][nw[3]] > -nw[0]){ dist2[nw[1]][nw[2]][nw[3]] = -nw[0]; q.push(nw); } } } } void solve(){ cin >> w >> h >> a >> b >> c; cin >> n; for(auto &i:dist1) for(auto &j:i) j = infll; for(auto &i:dist2){ for(auto &j:i){ for(auto &l:j){ l = infll; } } } for(int i=0; i<n; i++){ cin >> kek[i].first >> kek[i].second; } calc1(); calc2(); cout << dist2[kek[n-1].first][kek[n-1].second][4] << endl; } signed main(){ fast_io(); // ;(time(NULL)); cout << fixed << setprecision(10); int q = 1; // cin >> q; while(q--) solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...