oj.uz

Submission #868178

# Submission time Handle Problem Language Result Execution time Memory
868178 2023-10-30T16:22:25 Z nnhzzz Soccer (JOI17_soccer) C++14
100 / 100
 321 ms 24840 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               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
 
//------------------------------------------------------------------------------------------------//
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 oo = 1e9,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][5];
pii a[N],st,en;
int n,m,A,B,C,k;
 
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();
    k = readInt();
    memset(dis,0x3f,sizeof dis); memset(dp,0x3f,sizeof dp);
    priority_queue<Node> heap; queue<pii> q;
    REP(i,1,k){
        a[i].fi = readInt(); a[i].se = readInt();
        dis[a[i].fi][a[i].se] = 0;
        q.emplace(a[i].fi,a[i].se);
    }
    st = a[1]; en = a[k];
    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){
        auto [w1,x,y,t] = 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)==false) continue;
                if(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));
            }
            continue;
        }
        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:120:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  120 |         auto [x,y] = q.front(); q.pop();
      |              ^
soccer.cpp:132:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  132 |         auto [w1,x,y,t] = heap.top(); heap.pop();
      |              ^
soccer.cpp: In function 'int main()':
soccer.cpp:156:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  156 |         freopen(name".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
soccer.cpp:157:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  157 |         freopen(name".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
soccer.cpp:161:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  161 |         freopen(name1".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
soccer.cpp:162:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  162 |         freopen(name1".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 16116 KB Output is correct
2 Correct 2 ms 13912 KB Output is correct
3 Correct 189 ms 22928 KB Output is correct
4 Correct 209 ms 23784 KB Output is correct
5 Correct 30 ms 14056 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 201 ms 22564 KB Output is correct
2 Correct 256 ms 23484 KB Output is correct
3 Correct 158 ms 23988 KB Output is correct
4 Correct 188 ms 24108 KB Output is correct
5 Correct 150 ms 22720 KB Output is correct
6 Correct 172 ms 22468 KB Output is correct
7 Correct 184 ms 22980 KB Output is correct
8 Correct 248 ms 22792 KB Output is correct
9 Correct 250 ms 22716 KB Output is correct
10 Correct 30 ms 16332 KB Output is correct
11 Correct 257 ms 22968 KB Output is correct
12 Correct 226 ms 23232 KB Output is correct
13 Correct 144 ms 22272 KB Output is correct
14 Correct 283 ms 23908 KB Output is correct
15 Correct 171 ms 22588 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 16116 KB Output is correct
2 Correct 2 ms 13912 KB Output is correct
3 Correct 189 ms 22928 KB Output is correct
4 Correct 209 ms 23784 KB Output is correct
5 Correct 30 ms 14056 KB Output is correct
6 Correct 201 ms 22564 KB Output is correct
7 Correct 256 ms 23484 KB Output is correct
8 Correct 158 ms 23988 KB Output is correct
9 Correct 188 ms 24108 KB Output is correct
10 Correct 150 ms 22720 KB Output is correct
11 Correct 172 ms 22468 KB Output is correct
12 Correct 184 ms 22980 KB Output is correct
13 Correct 248 ms 22792 KB Output is correct
14 Correct 250 ms 22716 KB Output is correct
15 Correct 30 ms 16332 KB Output is correct
16 Correct 257 ms 22968 KB Output is correct
17 Correct 226 ms 23232 KB Output is correct
18 Correct 144 ms 22272 KB Output is correct
19 Correct 283 ms 23908 KB Output is correct
20 Correct 171 ms 22588 KB Output is correct
21 Correct 41 ms 14552 KB Output is correct
22 Correct 291 ms 23860 KB Output is correct
23 Correct 268 ms 19140 KB Output is correct
24 Correct 321 ms 19492 KB Output is correct
25 Correct 252 ms 23200 KB Output is correct
26 Correct 262 ms 24840 KB Output is correct
27 Correct 127 ms 15964 KB Output is correct
28 Correct 114 ms 16464 KB Output is correct
29 Correct 212 ms 19784 KB Output is correct
30 Correct 115 ms 15704 KB Output is correct
31 Correct 226 ms 23740 KB Output is correct
32 Correct 304 ms 24708 KB Output is correct
33 Correct 210 ms 24008 KB Output is correct
34 Correct 314 ms 23980 KB Output is correct
35 Correct 99 ms 15952 KB Output is correct