oj.uz

답안 #361254

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
361254 2021-01-29T00:41:07 Z jainbot27 Soccer (JOI17_soccer) C++17
30 / 100
 3000 ms 69288 KB 
#include <bits/stdc++.h>
using namespace std;

#define f first
#define s second
#define pb push_back
#define ar array
#define all(x) x.begin(), x.end()
#define siz(x) (int)x.size()

#define FOR(x, y, z) for(int x = (y); x < (z); x++)
#define ROF(x, z, y) for(int x = (y-1); x >= (z); x--)
#define F0R(x, z) FOR(x, 0, z)
#define R0F(x, z) ROF(x, 0, z)
#define trav(x, y) for(auto&x:y)

using ll = long long;
using vi = vector<int>;
using vl = vector<long long>;
using pii = pair<int, int>;
using vpii = vector<pair<int, int>>;

template<class T> inline bool ckmin(T&a, T b) {return b < a ? a = b, 1 : 0;}
template<class T> inline bool ckmax(T&a, T b) {return b > a ? a = b, 1 : 0;}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const char nl = '\n';
const int mxK = 100001;
const int mxN = 501;
const int MOD = 1e9 + 7;
const long long infLL = 1e18;

using node = pair<ll, ar<int, 2>>;
int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};


ll A, B, C;
int n, m;
int k;
pii pts[mxK];
bool dude[mxN][mxN];
ll dist[mxN][mxN];
int near[mxN][mxN];

queue<pii> bfs;
priority_queue<node, vector<node>, greater<node>> pq;

int32_t main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

    memset(near, 0x3f, sizeof(near));
    cin >> n >> m >> A >> B >> C >> k;
    n++; m++;
    F0R(i, k){
        cin >> pts[i].f >> pts[i].s;
        near[pts[i].f][pts[i].s] = 0;
        bfs.push({pts[i].f, pts[i].s});
    }
    while(!bfs.empty()){
        pii x = bfs.front();
        bfs.pop();
        F0R(i, 4){
            pii nx = x;
            nx.f += dx[i];
            nx.s += dy[i];
            if(nx.f < 0 || nx.f >= n || nx.s < 0 || nx.s >= m) continue;
            if(ckmin(near[nx.f][nx.s], near[x.f][x.s]+1)){
                bfs.push(nx);
            }
        } 
    }
    F0R(i, n){
        F0R(j, m){
            dist[i][j] = infLL;
        }
    }
    dist[pts[0].f][pts[0].s] = 0;
    pq.push({0, {pts[0].f, pts[0].s}});

    while(!pq.empty()){
        node U = pq.top();
        ll du = U.f;
        ar<int, 2> u = U.s;
        pq.pop();
        if(du!=dist[u[0]][u[1]]){
            continue;
        }
        F0R(i, n){
            if(ckmin(dist[i][u[1]], dist[u[0]][u[1]]+C*abs(u[0]-i))){
                pq.push({dist[i][u[1]], {i, u[1]}});
            }
            if(ckmin(dist[i][u[1]], dist[u[0]][u[1]]+B+A*abs(u[0]-i)+C*near[i][u[1]])){
                pq.push({dist[i][u[1]], {i, u[1]}});
            }
        }
        F0R(j, m){
            if(ckmin(dist[u[0]][j], du+C*abs(u[1]-j))){
                pq.push({dist[u[0]][j], {u[0], j}});
            }
            if(ckmin(dist[u[0]][j], du+B+A*abs(u[1]-j)+C*(near[u[0]][j]))){
                pq.push({dist[u[0]][j], {u[0], j}});
            }
        }
    } 
    //F0R(i, n){
    //    F0R(j, m){
    //        cout << near[i][j] << ' ';
    //    }
    //    cout << nl;
    //}
    //F0R(i, n){
    //    F0R(j, m){
    //        cout << dist[i][j] << ' ';
    //    }
    //    cout << nl;
    //}
    cout << dist[pts[k-1].f][pts[k-1].s] << nl;

    return 0;
}

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 181 ms 6752 KB Output is correct
2 Correct 1 ms 1388 KB Output is correct
3 Correct 1219 ms 11608 KB Output is correct
4 Execution timed out 3033 ms 69288 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1577 ms 20096 KB Output is correct
2 Correct 1511 ms 19932 KB Output is correct
3 Correct 946 ms 11228 KB Output is correct
4 Correct 1159 ms 11868 KB Output is correct
5 Correct 1135 ms 11756 KB Output is correct
6 Correct 1215 ms 11612 KB Output is correct
7 Correct 1392 ms 19912 KB Output is correct
8 Correct 1367 ms 20060 KB Output is correct
9 Correct 1467 ms 19912 KB Output is correct
10 Correct 127 ms 5472 KB Output is correct
11 Correct 1405 ms 20048 KB Output is correct
12 Correct 1441 ms 19912 KB Output is correct
13 Correct 779 ms 11228 KB Output is correct
14 Correct 1497 ms 19912 KB Output is correct
15 Correct 1046 ms 11736 KB Output is correct

Subtask #3
0 / 65.0

# 결과 실행 시간 메모리 Grader output
1 Correct 181 ms 6752 KB Output is correct
2 Correct 1 ms 1388 KB Output is correct
3 Correct 1219 ms 11608 KB Output is correct
4 Execution timed out 3033 ms 69288 KB Time limit exceeded
5 Halted 0 ms 0 KB -