oj.uz

Submission #173236

# Submission time Handle Problem Language Result Execution time Memory
173236 2020-01-03T15:58:03 Z mhy908 Soccer (JOI17_soccer) C++14
100 / 100
 912 ms 34820 KB 
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define all(x) x.begin(), x.end()
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef pair<LL, LL> pll;
const LL llinf=9000000000000000000;
const int inf=2000000000;
int n, h, w;
LL a, b, c;
pii point[100010];
vector<pair<int, LL> > link[800000];
priority_queue<pair<int, pii> > befpq;
priority_queue<pair<LL, pair<pii, int> > > pq;
int d[510][510];
int mx[]={1, 0, -1, 0}, my[]={0, 1, 0, -1};
bool ch[510][510][5];
int main()
{
    scanf("%d %d", &h, &w);
    scanf("%lld %lld %lld", &a, &b, &c);
    scanf("%d", &n);
    h++;
    w++;
    for(int i=1; i<=n; i++){
        scanf("%d %d", &point[i].F, &point[i].S);
        point[i].F++;
        point[i].S++;
        befpq.push(mp(0, point[i]));
    }
    for(int i=1; i<=h; i++)
        for(int j=1; j<=w; j++)
            d[i][j]=inf;
    while(!befpq.empty()){
        auto here=befpq.top();
        befpq.pop();
        here.F*=-1;
        if(here.S.F<1||here.S.S<1||here.S.F>h||here.S.S>w)continue;
        if(here.F>=d[here.S.F][here.S.S])continue;
        d[here.S.F][here.S.S]=here.F;
        for(int i=0; i<4; i++){
            befpq.push(mp(-here.F-1, mp(here.S.F+mx[i], here.S.S+my[i])));
        }
    }
    pq.push(mp(0, mp(point[1], 1)));
    while(!pq.empty()){
        auto here=pq.top();
        pq.pop();
        here.F*=-1;
        if(ch[here.S.F.F][here.S.F.S][here.S.S])continue;
        if(here.S.F.F<1||here.S.F.F>h||here.S.F.S<1||here.S.F.S>w)continue;
        ch[here.S.F.F][here.S.F.S][here.S.S]=true;
        if(here.S.F==point[n]&&here.S.S==1){
            printf("%lld", here.F);
            return 0;
        }
        if(here.S.S==1){
            pq.push(mp(-here.F-b, mp(here.S.F, 2)));
            pq.push(mp(-here.F-b, mp(here.S.F, 3)));
            for(int i=0; i<4; i++){
                pq.push(mp(-here.F-c, mp(mp(here.S.F.F+mx[i], here.S.F.S+my[i]), 1)));
            }
        }
        if(here.S.S==2){
            pq.push(mp(-here.F-d[here.S.F.F][here.S.F.S]*c, mp(here.S.F, 1)));
            pq.push(mp(-here.F-a, mp(mp(here.S.F.F+1, here.S.F.S), 2)));
            pq.push(mp(-here.F-a, mp(mp(here.S.F.F-1, here.S.F.S), 2)));
        }
        if(here.S.S==3){
            pq.push(mp(-here.F-d[here.S.F.F][here.S.F.S]*c, mp(here.S.F, 1)));
            pq.push(mp(-here.F-a, mp(mp(here.S.F.F, here.S.F.S+1), 3)));
            pq.push(mp(-here.F-a, mp(mp(here.S.F.F, here.S.F.S-1), 3)));
        }
    }
}

Compilation message

soccer.cpp: In function 'int main()':
soccer.cpp:24:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &h, &w);
     ~~~~~^~~~~~~~~~~~~~~~~
soccer.cpp:25:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld %lld %lld", &a, &b, &c);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
soccer.cpp:26:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
soccer.cpp:30:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &point[i].F, &point[i].S);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 22280 KB Output is correct
2 Correct 19 ms 19192 KB Output is correct
3 Correct 295 ms 27824 KB Output is correct
4 Correct 226 ms 24732 KB Output is correct
5 Correct 264 ms 23852 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 259 ms 24992 KB Output is correct
2 Correct 236 ms 23280 KB Output is correct
3 Correct 359 ms 27432 KB Output is correct
4 Correct 911 ms 27808 KB Output is correct
5 Correct 390 ms 34172 KB Output is correct
6 Correct 551 ms 33944 KB Output is correct
7 Correct 374 ms 34820 KB Output is correct
8 Correct 339 ms 34352 KB Output is correct
9 Correct 240 ms 23760 KB Output is correct
10 Correct 83 ms 25068 KB Output is correct
11 Correct 475 ms 34772 KB Output is correct
12 Correct 458 ms 34236 KB Output is correct
13 Correct 426 ms 33524 KB Output is correct
14 Correct 320 ms 28540 KB Output is correct
15 Correct 193 ms 23284 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 22280 KB Output is correct
2 Correct 19 ms 19192 KB Output is correct
3 Correct 295 ms 27824 KB Output is correct
4 Correct 226 ms 24732 KB Output is correct
5 Correct 264 ms 23852 KB Output is correct
6 Correct 259 ms 24992 KB Output is correct
7 Correct 236 ms 23280 KB Output is correct
8 Correct 359 ms 27432 KB Output is correct
9 Correct 911 ms 27808 KB Output is correct
10 Correct 390 ms 34172 KB Output is correct
11 Correct 551 ms 33944 KB Output is correct
12 Correct 374 ms 34820 KB Output is correct
13 Correct 339 ms 34352 KB Output is correct
14 Correct 240 ms 23760 KB Output is correct
15 Correct 83 ms 25068 KB Output is correct
16 Correct 475 ms 34772 KB Output is correct
17 Correct 458 ms 34236 KB Output is correct
18 Correct 426 ms 33524 KB Output is correct
19 Correct 320 ms 28540 KB Output is correct
20 Correct 193 ms 23284 KB Output is correct
21 Correct 149 ms 21364 KB Output is correct
22 Correct 663 ms 28024 KB Output is correct
23 Correct 750 ms 34216 KB Output is correct
24 Correct 591 ms 28868 KB Output is correct
25 Correct 574 ms 34052 KB Output is correct
26 Correct 726 ms 28860 KB Output is correct
27 Correct 618 ms 28928 KB Output is correct
28 Correct 907 ms 34232 KB Output is correct
29 Correct 912 ms 31680 KB Output is correct
30 Correct 655 ms 29240 KB Output is correct
31 Correct 297 ms 28644 KB Output is correct
32 Correct 426 ms 30700 KB Output is correct
33 Correct 535 ms 34200 KB Output is correct
34 Correct 269 ms 25492 KB Output is correct
35 Correct 886 ms 25264 KB Output is correct