oj.uz

Submission #685421

# Submission time Handle Problem Language Result Execution time Memory
685421 2023-01-24T10:36:23 Z coffee5427 Soccer (JOI17_soccer) C++17
100 / 100
 672 ms 105876 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 34872 KB Output is correct
2 Correct 5 ms 12372 KB Output is correct
3 Correct 393 ms 102944 KB Output is correct
4 Correct 465 ms 103040 KB Output is correct
5 Correct 83 ms 44688 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 639 ms 103264 KB Output is correct
2 Correct 586 ms 103352 KB Output is correct
3 Correct 359 ms 85932 KB Output is correct
4 Correct 350 ms 103060 KB Output is correct
5 Correct 392 ms 86096 KB Output is correct
6 Correct 392 ms 103048 KB Output is correct
7 Correct 584 ms 103680 KB Output is correct
8 Correct 478 ms 103464 KB Output is correct
9 Correct 583 ms 103732 KB Output is correct
10 Correct 72 ms 28488 KB Output is correct
11 Correct 589 ms 103776 KB Output is correct
12 Correct 571 ms 103368 KB Output is correct
13 Correct 281 ms 85816 KB Output is correct
14 Correct 574 ms 103756 KB Output is correct
15 Correct 448 ms 86712 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 34872 KB Output is correct
2 Correct 5 ms 12372 KB Output is correct
3 Correct 393 ms 102944 KB Output is correct
4 Correct 465 ms 103040 KB Output is correct
5 Correct 83 ms 44688 KB Output is correct
6 Correct 639 ms 103264 KB Output is correct
7 Correct 586 ms 103352 KB Output is correct
8 Correct 359 ms 85932 KB Output is correct
9 Correct 350 ms 103060 KB Output is correct
10 Correct 392 ms 86096 KB Output is correct
11 Correct 392 ms 103048 KB Output is correct
12 Correct 584 ms 103680 KB Output is correct
13 Correct 478 ms 103464 KB Output is correct
14 Correct 583 ms 103732 KB Output is correct
15 Correct 72 ms 28488 KB Output is correct
16 Correct 589 ms 103776 KB Output is correct
17 Correct 571 ms 103368 KB Output is correct
18 Correct 281 ms 85816 KB Output is correct
19 Correct 574 ms 103756 KB Output is correct
20 Correct 448 ms 86712 KB Output is correct
21 Correct 90 ms 44364 KB Output is correct
22 Correct 610 ms 103356 KB Output is correct
23 Correct 604 ms 92860 KB Output is correct
24 Correct 655 ms 101484 KB Output is correct
25 Correct 484 ms 103228 KB Output is correct
26 Correct 506 ms 103580 KB Output is correct
27 Correct 294 ms 101156 KB Output is correct
28 Correct 284 ms 101916 KB Output is correct
29 Correct 451 ms 103020 KB Output is correct
30 Correct 277 ms 101476 KB Output is correct
31 Correct 600 ms 103608 KB Output is correct
32 Correct 672 ms 105876 KB Output is correct
33 Correct 399 ms 102952 KB Output is correct
34 Correct 669 ms 103724 KB Output is correct
35 Correct 265 ms 101808 KB Output is correct