oj.uz

Submission #143346

# Submission time Handle Problem Language Result Execution time Memory
143346 2019-08-13T17:33:26 Z osaaateiasavtnl Soccer (JOI17_soccer) C++14
5 / 100
 308 ms 24956 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define ii pair <int, int>
#define app push_back
#define all(a) a.begin(), a.end()
#define bp __builtin_popcount
#define x first
#define y second
const int N = 507, INF = 1e18 + 7, MAXP = 1e5 + 7;
struct State {
    int x, y, k, c; bool t;
    bool const operator < (const State s) const { return c < s.c; }
};
vector <ii> v = { {0, -1}, {0, 1}, {-1, 0}, {1, 0} };
int n, m, A, B, C, P;
bool check(int i, int j) { return 0 <= i && 0 <= j && i <= n && j <= m; }
bool us[N][N]; int dist[N][N];
void bfs() {
    queue <ii> q;
    for (int i = 0; i <= n; ++i) {
        for (int j = 0; j <= m; ++j) {
            dist[i][j] = INF;
            if (us[i][j]) { dist[i][j] = 0; q.push({i, j}); }
        }
    }
    while (q.size()) {
        auto p = q.front(); q.pop();
        for (auto e : v) {
            if (check(p.x + e.x, p.y + e.y) && dist[p.x][p.y] + 1 < dist[p.x + e.x][p.y + e.y]) {
                dist[p.x + e.x][p.y + e.y] = dist[p.x][p.y] + 1;
                q.push({p.x + e.x, p.y + e.y});
            }
        }
    }
}
multiset <State> ms;
ii f[MAXP];
int dp1[N][N][4], dp2[N][N];
void upd(int x, int y, int k, int c) {
    if (check(x, y) && c < dp1[x][y][k]) {
        if (dp1[x][y][k] != INF) ms.erase(ms.find({x, y, k, dp1[x][y][k], 0}));
        dp1[x][y][k] = c;
        ms.insert({x, y, k, dp1[x][y][k], 0});
    }
}
void upd(int x, int y, int c) {
    if (check(x, y) && c < dp2[x][y]) {
        if (dp2[x][y] != INF) ms.erase(ms.find({x, y, -1, dp2[x][y], 1}));
        dp2[x][y] = c;
        ms.insert({x, y, -1, dp2[x][y], 1});
    }
}
void print(State s) {
    #ifdef HOME
    cout << s.x << ' ' << s.y << ' ' << s.k << ' ' << s.c << '\n';
    #endif
}
signed main() {
    #ifdef HOME
    freopen("input.txt", "r", stdin);
    #else
    ios_base::sync_with_stdio(0); cin.tie(0);
    #endif
    cin >> n >> m >> A >> B >> C >> P;  
    for (int i = 0; i < P; ++i) { int x, y; cin >> x >> y; us[x][y] = 1; f[i] = {x, y}; }
    bfs();
    for (int i = 0; i < N; ++i) for (int j = 0; j < N; ++j) for (int k = 0; k < 4; ++k) dp1[i][j][k] = INF;
    for (int i = 0; i < N; ++i) for (int j = 0; j < N; ++j) dp2[i][j] = INF;
    upd(f[0].x, f[0].y, 0);
    while (ms.size()) {
        auto s = *ms.begin(); ms.erase(ms.begin());
        //print(s);
        if (s.x == f[P - 1].x && s.y == f[P - 1].y) { cout << s.c << '\n'; exit(0); }
        if (s.t) {
            for (auto e : v) upd(s.x + e.x, s.y + e.y, s.c + C);
            for (int i = 0; i < 4; ++i) upd(s.x, s.y, i, s.c + B);
        }
        else {
            upd(s.x, s.y, s.c + C * dist[s.x][s.y]);
            upd(s.x + v[s.k].x, s.y + v[s.k].y, s.k, s.c + A);   
        }
    }
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 14328 KB Output is correct
2 Correct 11 ms 10488 KB Output is correct
3 Correct 142 ms 23816 KB Output is correct
4 Correct 74 ms 18808 KB Output is correct
5 Correct 58 ms 11896 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 17528 KB Output is correct
2 Correct 49 ms 16120 KB Output is correct
3 Correct 190 ms 24416 KB Output is correct
4 Correct 308 ms 23108 KB Output is correct
5 Incorrect 215 ms 24956 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 14328 KB Output is correct
2 Correct 11 ms 10488 KB Output is correct
3 Correct 142 ms 23816 KB Output is correct
4 Correct 74 ms 18808 KB Output is correct
5 Correct 58 ms 11896 KB Output is correct
6 Correct 62 ms 17528 KB Output is correct
7 Correct 49 ms 16120 KB Output is correct
8 Correct 190 ms 24416 KB Output is correct
9 Correct 308 ms 23108 KB Output is correct
10 Incorrect 215 ms 24956 KB Output isn't correct
11 Halted 0 ms 0 KB -