Submission #536444

#	Time	Username	Problem	Language	Result	Execution time	Memory
536444		qwerasdfzxcl	Soccer (JOI17_soccer)	C++14	100 / 100	732 ms	17448 KiB

soccer

#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 (stderr)

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 / 5
• Subtask 2: 30 / 30
• Subtask 3: 65 / 65