oj.uz

Submission #868172

# Submission time Handle Problem Language Result Execution time Memory
868172 2023-10-30T16:15:25 Z nnhzzz Soccer (JOI17_soccer) C++14
100 / 100
 409 ms 35396 KB 
// cre: Nguyen Ngoc Hung - Train VOI 2024 :>

#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <unordered_set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <cstring>
#include <unordered_map>
#include <cmath>
#include <array>
#include <cassert>
#include <random>

using namespace std;

#define        __nnhzzz__  signed main()
#define          BIT(i,j)  ((i>>j)&1LL)
#define           MASK(i)  (1LL<<i)
#define            ALL(x)  (x).begin(),(x).end()
#define             SZ(x)  (int)(x).size()
#define                fi  first
#define                se  second
#define                ll  long long
#define                vi  vector<int>
#define               vvi  vector<vi>
#define              vvvi  vector<vvi>
#define               pii  pair<int,int>
#define              vpii  vector<pii>
#define REPDIS(i,be,en,j)  for(int i = (be); i<=(en); i+=j)
#define     REPD(i,be,en)  for(int i = (be); i>=(en); i--)
#define      REP(i,be,en)  for(int i = (be); i<=(en); i++)
#define               int  ll
#define                MP  make_pair

//------------------------------------------------------------------------------------------------//
int readInt(){
    char c;
    do{ c = getchar(); }while(c!='-' && !isdigit(c));
    bool neg = (c=='-');
    int res = neg?0:c-'0';
    while(isdigit(c=getchar())) res = (res<<3)+(res<<1)+(c-'0');
    return neg?-res:res;
}
//------------------------------------------------------------------------------------------------//
const int inf = 1e18,LOG = 20,MAXN = 5e2+7,N = 1e5+3;
const int MOD = 1e9+7,MOD1 = 1e9+207,MOD2 = 1e9+407,MOD3 = 998244353;
const int dx[] = {0,0,-1,1},dy[] = {-1,1,0,0};
//------------------------------------------------------------------------------------------------//
template<typename T1, typename T2> bool mini(T1 &a, T2 b){if(a>b){a=b;return true;}return false;}
template<typename T1, typename T2> bool maxi(T1 &a, T2 b){if(a<b){a=b;return true;}return false;}
template<typename T> T gcd(T a, T b) { while(b) { a %= b; swap(a,b); } return a; }
template<typename T> T lcm(T a, T b) { return a/gcd(a,b)*b; }
//------------------------------------------------------------------------------------------------//

/*
----------------------------------------------------------------
    END OF TEMPLATE
----------------------------------------------------------------
    Nguyen Ngoc Hung - nnhzzz
    Training for VOI24 gold medal
----------------------------------------------------------------
*/

struct Node{
    int w,x,y,t;
    Node(int _w, int _x, int _y, int _t):w(_w),x(_x),y(_y),t(_t){}
    bool operator < (const Node &other) const {
        return w>other.w;
    }
};

// int dis[MAXN][MAXN],dp[MAXN][MAXN][6];
pii st,en;
int n,m,A,B,C;

bool ok(int x, int y){
    return (x>=0 && y>=0 && x<=n && y<=m);
}

void solve(){
    n = readInt(); m = readInt();
    A = readInt(); B = readInt(); C = readInt();
    int tmp = readInt();
    // memset(dis,0x3f,sizeof dis); memset(dp,0x3f,sizeof dp);
    vvvi dp(n+3,vvi(m+3,vi(6,inf))); vvi dis(n+3,vi(m+3,inf));
    priority_queue<Node> heap; queue<pii> q;
    REP(i,1,tmp){
        int x = readInt(),y = readInt();
        dis[x][y] = 0; q.emplace(x,y);
        if(i==1) st = MP(x,y);
        if(i==tmp) en = MP(x,y);
    }
    while(SZ(q)!=0){
        auto [x,y] = q.front(); q.pop();
        REP(i,0,3){
            int nx = x+dx[i],ny = y+dy[i];
            if(ok(nx,ny)==false) continue;
            if(mini(dis[nx][ny],dis[x][y]+1)){
                q.emplace(nx,ny);
            }
        }
    }
    heap.push(Node(0,st.fi,st.se,4));
    dp[st.fi][st.se][4] = 0; // i,j,4 - den o i,j dang du bong
    while(SZ(heap)!=0){
        Node node = heap.top(); heap.pop();
        int w1 = node.w,x = node.x,y = node.y,t = node.t;
        if(dp[x][y][t]!=w1) continue;
        if(t==4){
            REP(i,0,3){
                int nx = x+dx[i],ny = y+dy[i];
                if(ok(nx,ny)==true && mini(dp[nx][ny][4],dp[x][y][4]+C)) heap.push(Node(dp[nx][ny][4],nx,ny,4));
                if(mini(dp[x][y][i],dp[x][y][4]+B)) heap.push(Node(dp[x][y][i],x,y,i));
            }
        }else{
            int nx = x+dx[t],ny = y+dy[t];
            if(ok(nx,ny)==true && mini(dp[nx][ny][t],dp[x][y][t]+A)) heap.push(Node(dp[nx][ny][t],nx,ny,t));
            if(mini(dp[x][y][4],dp[x][y][t]+dis[x][y]*C)) heap.push(Node(dp[x][y][4],x,y,4));
        }
    }
    cout << dp[en.fi][en.se][4];
}

__nnhzzz__{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    #define name "test"
    if(fopen(name".inp","r")){
        freopen(name".inp","r",stdin);
        freopen(name".out","w",stdout);
    }
    #define name1 "nnhzzz"
    if(fopen(name1".inp","r")){
        freopen(name1".inp","r",stdin);
        freopen(name1".out","w",stdout);
    }

    int test = 1;

    while(test--){
      solve();
    }
    cerr << "\nTime elapsed: " << 1000*clock()/CLOCKS_PER_SEC << "ms\n";
    return 0;
}

Compilation message

soccer.cpp: In function 'void solve()':
soccer.cpp:123:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  123 |         auto [x,y] = q.front(); q.pop();
      |              ^
soccer.cpp: In function 'int main()':
soccer.cpp:158:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  158 |         freopen(name".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
soccer.cpp:159:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  159 |         freopen(name".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
soccer.cpp:163:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  163 |         freopen(name1".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
soccer.cpp:164:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  164 |         freopen(name1".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 8404 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 249 ms 32672 KB Output is correct
4 Correct 269 ms 33976 KB Output is correct
5 Correct 42 ms 9308 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 299 ms 33528 KB Output is correct
2 Correct 277 ms 33204 KB Output is correct
3 Correct 199 ms 28620 KB Output is correct
4 Correct 189 ms 32756 KB Output is correct
5 Correct 206 ms 29112 KB Output is correct
6 Correct 205 ms 32776 KB Output is correct
7 Correct 409 ms 34044 KB Output is correct
8 Correct 260 ms 32772 KB Output is correct
9 Correct 329 ms 33232 KB Output is correct
10 Correct 33 ms 6608 KB Output is correct
11 Correct 305 ms 33280 KB Output is correct
12 Correct 298 ms 33500 KB Output is correct
13 Correct 158 ms 28872 KB Output is correct
14 Correct 306 ms 33788 KB Output is correct
15 Correct 226 ms 30012 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 8404 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 249 ms 32672 KB Output is correct
4 Correct 269 ms 33976 KB Output is correct
5 Correct 42 ms 9308 KB Output is correct
6 Correct 299 ms 33528 KB Output is correct
7 Correct 277 ms 33204 KB Output is correct
8 Correct 199 ms 28620 KB Output is correct
9 Correct 189 ms 32756 KB Output is correct
10 Correct 206 ms 29112 KB Output is correct
11 Correct 205 ms 32776 KB Output is correct
12 Correct 409 ms 34044 KB Output is correct
13 Correct 260 ms 32772 KB Output is correct
14 Correct 329 ms 33232 KB Output is correct
15 Correct 33 ms 6608 KB Output is correct
16 Correct 305 ms 33280 KB Output is correct
17 Correct 298 ms 33500 KB Output is correct
18 Correct 158 ms 28872 KB Output is correct
19 Correct 306 ms 33788 KB Output is correct
20 Correct 226 ms 30012 KB Output is correct
21 Correct 44 ms 9688 KB Output is correct
22 Correct 335 ms 33624 KB Output is correct
23 Correct 320 ms 27584 KB Output is correct
24 Correct 341 ms 30112 KB Output is correct
25 Correct 307 ms 33576 KB Output is correct
26 Correct 308 ms 33708 KB Output is correct
27 Correct 152 ms 26204 KB Output is correct
28 Correct 159 ms 27328 KB Output is correct
29 Correct 302 ms 32560 KB Output is correct
30 Correct 133 ms 26960 KB Output is correct
31 Correct 326 ms 32696 KB Output is correct
32 Correct 391 ms 35396 KB Output is correct
33 Correct 236 ms 32952 KB Output is correct
34 Correct 377 ms 33336 KB Output is correct
35 Correct 117 ms 26728 KB Output is correct