oj.uz

Submission #536444

# Submission time Handle Problem Language Result Execution time Memory
536444 2022-03-13T10:50:27 Z qwerasdfzxcl Soccer (JOI17_soccer) C++14
100 / 100
 732 ms 17448 KB 
#include <bits/stdc++.h>

typedef long long ll;
using namespace std;
constexpr int INF = 1e9;
struct Vertex{
    int x, y, typ;
    ll d;
    Vertex(int _x, int _y, int _typ, ll _d): x(_x), y(_y), typ(_typ), d(_d) {}
    bool operator<(const Vertex &V) const{
        return d > V.d;
    }
};
pair<int, int> a[100100];
int dist[505][505], n, m, k, dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
bool visited[505][505][6];
ll A, B, C;

bool valid(int x, int y){
    return (1<=x && x<=n) && (1<=y && y<=m);
}

int myabs(int x){return x>0?x:-x;}
ll getdist(int x, int y){return C * (myabs(a[k].first - x) + myabs(a[k].second - y));}

void bfs(){
    for (int i=1;i<=n;i++){
        for (int j=1;j<=m;j++) dist[i][j] = INF;
    }

    queue<pair<int, int>> q;
    for (int i=1;i<=k;i++){
        dist[a[i].first][a[i].second] = 0;
        q.emplace(a[i].first, a[i].second);
    }
    while(!q.empty()){
        auto p = q.front(); q.pop();
        for (int i=0;i<4;i++){
            int nx = p.first + dx[i], ny = p.second + dy[i];
            if (!valid(nx, ny) || dist[nx][ny]!=INF) continue;
            dist[nx][ny] = dist[p.first][p.second] + 1;
            q.emplace(nx, ny);
        }
    }
}

void dijkstra(){
    priority_queue<Vertex> pq;
    pq.emplace(a[1].first, a[1].second, 5, 0);
    while(!pq.empty()){
        auto cur = pq.top(); pq.pop();
        if (visited[cur.x][cur.y][cur.typ]) continue;
        if (cur.typ==-1) {printf("%lld\n", cur.d); exit(0);}
        visited[cur.x][cur.y][cur.typ] = 1;

        if (cur.typ<4){
            int nx = cur.x + dx[cur.typ], ny = cur.y + dy[cur.typ];
            if (valid(nx, ny)) pq.emplace(nx, ny, cur.typ, cur.d + A);

            pq.emplace(cur.x, cur.y, 4, cur.d);
        }
        else if (cur.typ==4){
            pq.emplace(cur.x, cur.y, 5, cur.d + C * dist[cur.x][cur.y]);
            pq.emplace(-1, -1, -1, cur.d + getdist(cur.x, cur.y));
        }
        else{
            for (int i=0;i<4;i++){
                int nx = cur.x + dx[i], ny = cur.y + dy[i];
                if (!valid(nx, ny)) continue;

                pq.emplace(nx, ny, 5, cur.d + C);
                pq.emplace(cur.x, cur.y, i, cur.d + B);
            }
            pq.emplace(cur.x, cur.y, 4, cur.d);
        }
    }
    assert(0);
}

int main(){
    scanf("%d %d", &n, &m);
    n++, m++;
    scanf("%lld %lld %lld", &A, &B, &C);
    scanf("%d", &k);
    for (int i=1;i<=k;i++){
        scanf("%d %d", &a[i].first, &a[i].second);
        a[i].first++, a[i].second++;
    }
    bfs();
    dijkstra();
    return 0;
}

Compilation message

soccer.cpp: In function 'int main()':
soccer.cpp:81:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   81 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
soccer.cpp:83:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   83 |     scanf("%lld %lld %lld", &A, &B, &C);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
soccer.cpp:84:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   84 |     scanf("%d", &k);
      |     ~~~~~^~~~~~~~~~
soccer.cpp:86:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   86 |         scanf("%d %d", &a[i].first, &a[i].second);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 5032 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 122 ms 15200 KB Output is correct
4 Correct 46 ms 9068 KB Output is correct
5 Correct 142 ms 4800 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 9096 KB Output is correct
2 Correct 26 ms 6032 KB Output is correct
3 Correct 178 ms 14744 KB Output is correct
4 Correct 703 ms 15216 KB Output is correct
5 Correct 197 ms 15360 KB Output is correct
6 Correct 332 ms 15164 KB Output is correct
7 Correct 121 ms 15392 KB Output is correct
8 Correct 134 ms 15272 KB Output is correct
9 Correct 18 ms 4588 KB Output is correct
10 Correct 19 ms 5984 KB Output is correct
11 Correct 243 ms 15288 KB Output is correct
12 Correct 234 ms 15212 KB Output is correct
13 Correct 233 ms 14672 KB Output is correct
14 Correct 93 ms 15340 KB Output is correct
15 Correct 12 ms 4452 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 5032 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 122 ms 15200 KB Output is correct
4 Correct 46 ms 9068 KB Output is correct
5 Correct 142 ms 4800 KB Output is correct
6 Correct 45 ms 9096 KB Output is correct
7 Correct 26 ms 6032 KB Output is correct
8 Correct 178 ms 14744 KB Output is correct
9 Correct 703 ms 15216 KB Output is correct
10 Correct 197 ms 15360 KB Output is correct
11 Correct 332 ms 15164 KB Output is correct
12 Correct 121 ms 15392 KB Output is correct
13 Correct 134 ms 15272 KB Output is correct
14 Correct 18 ms 4588 KB Output is correct
15 Correct 19 ms 5984 KB Output is correct
16 Correct 243 ms 15288 KB Output is correct
17 Correct 234 ms 15212 KB Output is correct
18 Correct 233 ms 14672 KB Output is correct
19 Correct 93 ms 15340 KB Output is correct
20 Correct 12 ms 4452 KB Output is correct
21 Correct 59 ms 2932 KB Output is correct
22 Correct 438 ms 15212 KB Output is correct
23 Correct 583 ms 15164 KB Output is correct
24 Correct 352 ms 15392 KB Output is correct
25 Correct 351 ms 15344 KB Output is correct
26 Correct 493 ms 15612 KB Output is correct
27 Correct 321 ms 10444 KB Output is correct
28 Correct 620 ms 11460 KB Output is correct
29 Correct 732 ms 17048 KB Output is correct
30 Correct 377 ms 10688 KB Output is correct
31 Correct 68 ms 9192 KB Output is correct
32 Correct 161 ms 17448 KB Output is correct
33 Correct 346 ms 15240 KB Output is correct
34 Correct 33 ms 6128 KB Output is correct
35 Correct 529 ms 11080 KB Output is correct