Submission #685421

#	Time	Username	Problem	Language	Result	Execution time	Memory
685421		coffee5427	Soccer (JOI17_soccer)	C++17	100 / 100	672 ms	105876 KiB

soccer

#include <queue>
#include <vector>
#include <stdio.h>
#include <iostream>
#include <algorithm>
#define INF 0x3f3f3f3f
#define MAX 0x7f7f7f7f7f7f7f7f
using namespace std;
typedef long long ll;
const int W = 505;
const int N = 100005;

struct Node{ int x; ll y; };
struct player{ int x, y; }P[N];
struct Edge{ int to, next; ll weight; }edge[W * W * 36];
struct cmp{ bool operator()(Node x, Node y){ return x.y > y.y; } };

ll dis[W * W * 6], ans = MAX;
bool vis[W][W], vis2[W * W * 6];
int h, w, a, b, c, n, sum, cnt = 1;
int dx[4] = { 1, -1, 0, 0 };
int dy[4] = { 0, 0, 1, -1 };
int head[W * W * 6], dt[W][W];
int ctt = 0;

template<typename T> inline void read(T &x)
{
    x = 0; char ch = getchar(); bool flag = false;
    while(ch < '0' || ch > '9'){if(ch == '-') flag = true; ch = getchar();}
    while('0' <= ch && ch <= '9'){x = (x << 3) + (x << 1) + (ch ^ 48); ch = getchar();}
    if(flag) x = -x;
}

inline void add(int u, int v, ll w)
{
  // cout << "u:" << u << ",v:" << v << ",w:" << w << "\n";
  //   ctt++;
  //   if (ctt > 20) exit(0);
    edge[cnt].to = v, edge[cnt].weight = w;
    edge[cnt].next = head[u], head[u] = cnt++;
}

inline ll Min(ll x, ll y){ return x < y ? x : y; }
inline int id(int x, int y){ return x * (w + 1) + y; } //用一個數字表示一個平面座標 

inline void Manhattan_Distance()
{
    queue<player> q;
    for(register int i = 0;i <= h;i++) for(register int j = 0;j <= w;j++) dt[i][j] = INF;
    for(register int i = 1; i <= n; i++){ dt[P[i].x][P[i].y] = 0; q.push(P[i]); }
    while(!q.empty())
    {
        int x = q.front().x, y = q.front().y;
        q.pop(); vis[x][y] = false;
        for(register int i = 0; i < 4; i++)
        {
            int xx = x + dx[i], yy = y + dy[i];
            if(xx >= 0 && xx <= h && yy >= 0 && yy <= w && dt[xx][yy] > dt[x][y] + 1)
            {
                dt[xx][yy] = dt[x][y] + 1;
                if(!vis[xx][yy])
                {
                    player graph;
                    graph.x = xx, graph.y = yy;
                    q.push(graph);  vis[xx][yy] = true;
                }
            }
        }
    }
}

inline void Dijkstra()
{
    priority_queue<Node, vector<Node>, cmp> q;
    for(register int i = 0;i <= W * W * 6;i++) dis[i] = MAX;
    Node graph; graph.x = id(P[1].x, P[1].y) + 4 * sum, graph.y = 0;
    q.push(graph); dis[id(P[1].x, P[1].y) + 4 * sum] = 0;
    while(!q.empty())
    {
        int x = q.top().x;
        q.pop(); if(!vis2[x])
        {
            vis2[x] = true;
            for(register int i = head[x];i != 0;i = edge[i].next)
            {
                int v = edge[i].to;
                if (dis[v] > dis[x] + edge[i].weight)
                {
                    dis[v] = dis[x] + edge[i].weight; Node graph;
                    graph.x = v, graph.y = dis[v];
                    q.push(graph);
                }
            }
        }
    }
}

int main()
{
    read(h), read(w), read(a), read(b), read(c), read(n);
    for(register int i = 1; i <= n; i++) read(P[i].x), read(P[i].y);
    Manhattan_Distance();
    sum = (w + 1) * (h + 1); //因爲橫縱座標可以爲0，所以要+1
	//通過k * sum的表示方法拆點 
    for(register int i = 0; i <= h; i++)
    {
        for(register int j = 0; j <= w; j++)
        {
            int p = id(i, j);
            for(register int k = 0; k < 4; k++)
            {
              //cout << "p:" << p << ",k:" << k << ",sum:" << sum << "\n";
                add(p + k * sum, p + 4 * sum, 0); //球從滾動狀態（無人控球）到停止 
                add(p + 5 * sum, p + k * sum, b); //球從靜止狀態（有人控球）到將球傳出 
                add(p + 4 * sum, p + 5 * sum, c * (ll)dt[i][j]); //離球最近的球員（曼哈頓距離）跑過來控球 
				int xx = i + dx[k], yy = j + dy[k];
        // cout << "k:" << k << "\n";
        // cout << "p:" "(" << i << "," << j << ")" << "\n";
        // cout << "q:" << "(" << xx << "," << yy << ")" << "\n";
                if(xx >= 0 && yy >= 0 && xx <= h && yy <= w)
                {
                    int q = id(xx, yy);
                    add(p + k * sum, q + k * sum, a); //球從一個位置按照其方向滾到相鄰的位置（傳球） 
                    add(p + 5 * sum, q + 5 * sum, c); //球從一個位置按照其方向滾到相鄰的位置（帶球） 
                }
            }
        }
    }
    Dijkstra();
    for(register int i = 0; i < 6; i++)
    {
        ans = Min(ans, dis[id(P[n].x, P[n].y) + i * sum]);
    }
    //printf("%lld\n", dis[id(P[1].x, P[0].y) + 1 * sum]);
    printf("%lld\n", ans);
    return 0;
}

Compilation message (stderr)

soccer.cpp: In function 'void Manhattan_Distance()':
soccer.cpp:49:22: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   49 |     for(register int i = 0;i <= h;i++) for(register int j = 0;j <= w;j++) dt[i][j] = INF;
      |                      ^
soccer.cpp:49:57: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   49 |     for(register int i = 0;i <= h;i++) for(register int j = 0;j <= w;j++) dt[i][j] = INF;
      |                                                         ^
soccer.cpp:50:22: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   50 |     for(register int i = 1; i <= n; i++){ dt[P[i].x][P[i].y] = 0; q.push(P[i]); }
      |                      ^
soccer.cpp:55:26: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   55 |         for(register int i = 0; i < 4; i++)
      |                          ^
soccer.cpp: In function 'void Dijkstra()':
soccer.cpp:75:22: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   75 |     for(register int i = 0;i <= W * W * 6;i++) dis[i] = MAX;
      |                      ^
soccer.cpp:84:30: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   84 |             for(register int i = head[x];i != 0;i = edge[i].next)
      |                              ^
soccer.cpp: In function 'int main()':
soccer.cpp:101:22: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
  101 |     for(register int i = 1; i <= n; i++) read(P[i].x), read(P[i].y);
      |                      ^
soccer.cpp:105:22: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
  105 |     for(register int i = 0; i <= h; i++)
      |                      ^
soccer.cpp:107:26: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
  107 |         for(register int j = 0; j <= w; j++)
      |                          ^
soccer.cpp:110:30: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
  110 |             for(register int k = 0; k < 4; k++)
      |                              ^
soccer.cpp:130:22: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
  130 |     for(register int i = 0; i < 6; i++)
      |                      ^
soccer.cpp: In function 'void Dijkstra()':
soccer.cpp:75:55: warning: iteration 1530150 invokes undefined behavior [-Waggressive-loop-optimizations]
   75 |     for(register int i = 0;i <= W * W * 6;i++) dis[i] = MAX;
      |                                                       ^
soccer.cpp:75:30: note: within this loop
   75 |     for(register int i = 0;i <= W * W * 6;i++) dis[i] = MAX;
      |                            ~~^~~~~~~~~~~~
soccer.cpp:75:55: warning: 'void* __builtin_memset(void*, int, long unsigned int)' forming offset [12241200, 12241207] is out of the bounds [0, 12241200] of object 'dis' with type 'll [1530150]' {aka 'long long int [1530150]'} [-Warray-bounds]
   75 |     for(register int i = 0;i <= W * W * 6;i++) dis[i] = MAX;
      |                                                       ^
soccer.cpp:18:4: note: 'dis' declared here
   18 | ll dis[W * W * 6], ans = MAX;
      |    ^~~

• Subtask 1: 5 / 5
• Subtask 2: 30 / 30
• Subtask 3: 65 / 65