oj.uz

Submission #93931

# Submission time Handle Problem Language Result Execution time Memory
93931 2019-01-13T11:07:12 Z brcode Soccer (JOI17_soccer) C++14
100 / 100
 657 ms 28268 KB 
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
using namespace std;

long long n,m,a,b,c,t;
long long dx[5] = {-1,0,1,0};
long long dy[5] = {0,1,0,-1};
long long dis[550][550];
long long dist[550][550][7];
priority_queue<pair<pair<long long,long long>,pair<long long,long long>>> pq;
bool check(long long x ,long long y){
    if(x<0||y<0||x>n||y>m){
        return false;
    }
    return true;
}
void insert(long long x,long long y,long long t,long long d){
    if(!check(x,y)){
        return;
    }
   
    if(dist[x][y][t]>d){
        dist[x][y][t] = d;
        pq.push(make_pair(make_pair(-1*d,t),make_pair(x,y)));
    }
}
int main() {
    cin>>n>>m>>a>>b>>c>>t;
    for(long long i=0;i<=n;i++){
        for(long long j=0;j<=m;j++){
            for(long long k=0;k<=5;k++){
                dist[i][j][k] = 1e18;
                dis[i][j] = 1e18;
            }
        }
    }
    queue<pair<long long,long long>> q1;
    pair<long long,long long> start,end;
    for(long long i=0;i<t;i++){
        long long x,y;
        cin>>x>>y;
        if(i == 0){
            start = make_pair(x,y);
        }
        if(i==t-1){
            end = make_pair(x,y);
        }
        dis[x][y] = 0;
        q1.push(make_pair(x,y));
        
        
    }
    while(!q1.empty()){
        auto x= q1.front();
      
        q1.pop();
        for(long long i=0;i<4;i++){
            if(check(x.first+dx[i],x.second+dy[i]) && dis[x.first+dx[i]][x.second+dy[i]]>1e9){
                dis[x.first+dx[i]][x.second+dy[i]] = dis[x.first][x.second]+1;
                q1.push(make_pair(x.first+dx[i],x.second+dy[i]));
            }
        }
    }
    insert(start.first,start.second,4,0);
    while(!pq.empty()){
        auto hold= pq.top();
        
        pq.pop();
        long long x = hold.second.first;
        long long y = hold.second.second;
        long long distance = -1*hold.first.first;
        long long t = hold.first.second;
        
        if(dist[x][y][t]!=distance){
            continue;
        }
        if(t==4){
            for(long long i=0;i<4;i++){
                insert(x+dx[i],y+dy[i],4,distance+c);
                insert(x,y,i,distance+b);
            }
        }else{
            insert(x+dx[t],y+dy[t],t,distance+a);
            insert(x,y,4,distance+dis[x][y]*c);
        }
    }
    cout<<dist[end.first][end.second][4]<<endl;
    
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 8588 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 383 ms 25948 KB Output is correct
4 Correct 411 ms 25948 KB Output is correct
5 Correct 86 ms 8568 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 410 ms 25948 KB Output is correct
2 Correct 414 ms 25948 KB Output is correct
3 Correct 333 ms 22492 KB Output is correct
4 Correct 348 ms 25976 KB Output is correct
5 Correct 366 ms 23900 KB Output is correct
6 Correct 388 ms 25948 KB Output is correct
7 Correct 463 ms 26200 KB Output is correct
8 Correct 436 ms 25948 KB Output is correct
9 Correct 442 ms 26196 KB Output is correct
10 Correct 61 ms 8936 KB Output is correct
11 Correct 411 ms 26072 KB Output is correct
12 Correct 461 ms 25948 KB Output is correct
13 Correct 267 ms 22620 KB Output is correct
14 Correct 471 ms 26080 KB Output is correct
15 Correct 466 ms 24104 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 8588 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 383 ms 25948 KB Output is correct
4 Correct 411 ms 25948 KB Output is correct
5 Correct 86 ms 8568 KB Output is correct
6 Correct 410 ms 25948 KB Output is correct
7 Correct 414 ms 25948 KB Output is correct
8 Correct 333 ms 22492 KB Output is correct
9 Correct 348 ms 25976 KB Output is correct
10 Correct 366 ms 23900 KB Output is correct
11 Correct 388 ms 25948 KB Output is correct
12 Correct 463 ms 26200 KB Output is correct
13 Correct 436 ms 25948 KB Output is correct
14 Correct 442 ms 26196 KB Output is correct
15 Correct 61 ms 8936 KB Output is correct
16 Correct 411 ms 26072 KB Output is correct
17 Correct 461 ms 25948 KB Output is correct
18 Correct 267 ms 22620 KB Output is correct
19 Correct 471 ms 26080 KB Output is correct
20 Correct 466 ms 24104 KB Output is correct
21 Correct 99 ms 8564 KB Output is correct
22 Correct 516 ms 26056 KB Output is correct
23 Correct 616 ms 20200 KB Output is correct
24 Correct 536 ms 22120 KB Output is correct
25 Correct 483 ms 25992 KB Output is correct
26 Correct 517 ms 26208 KB Output is correct
27 Correct 367 ms 20216 KB Output is correct
28 Correct 351 ms 20728 KB Output is correct
29 Correct 493 ms 24180 KB Output is correct
30 Correct 297 ms 20216 KB Output is correct
31 Correct 536 ms 26136 KB Output is correct
32 Correct 657 ms 28268 KB Output is correct
33 Correct 403 ms 25968 KB Output is correct
34 Correct 548 ms 26068 KB Output is correct
35 Correct 268 ms 19960 KB Output is correct