oj.uz

답안 #868164

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
868164 2023-10-30T15:46:57 Z nnhzzz Soccer (JOI17_soccer) C++14
35 / 100
 253 ms 31704 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
#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 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;

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);
    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){
        const 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){
        const 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)==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:122:21: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  122 |         const 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

# 결과 실행 시간 메모리 Grader output
1 Correct 52 ms 16080 KB Output is correct
2 Correct 2 ms 13912 KB Output is correct
3 Correct 197 ms 23236 KB Output is correct
4 Correct 201 ms 22372 KB Output is correct
5 Correct 30 ms 14068 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 196 ms 23740 KB Output is correct
2 Correct 218 ms 22456 KB Output is correct
3 Correct 165 ms 23728 KB Output is correct
4 Correct 160 ms 23012 KB Output is correct
5 Correct 151 ms 23476 KB Output is correct
6 Correct 176 ms 22984 KB Output is correct
7 Correct 189 ms 23480 KB Output is correct
8 Correct 200 ms 23808 KB Output is correct
9 Correct 223 ms 22972 KB Output is correct
10 Correct 30 ms 16080 KB Output is correct
11 Correct 187 ms 24252 KB Output is correct
12 Correct 201 ms 22208 KB Output is correct
13 Correct 139 ms 23248 KB Output is correct
14 Correct 193 ms 22472 KB Output is correct
15 Correct 159 ms 24124 KB Output is correct

Subtask #3
0 / 65.0

# 결과 실행 시간 메모리 Grader output
1 Correct 52 ms 16080 KB Output is correct
2 Correct 2 ms 13912 KB Output is correct
3 Correct 197 ms 23236 KB Output is correct
4 Correct 201 ms 22372 KB Output is correct
5 Correct 30 ms 14068 KB Output is correct
6 Correct 196 ms 23740 KB Output is correct
7 Correct 218 ms 22456 KB Output is correct
8 Correct 165 ms 23728 KB Output is correct
9 Correct 160 ms 23012 KB Output is correct
10 Correct 151 ms 23476 KB Output is correct
11 Correct 176 ms 22984 KB Output is correct
12 Correct 189 ms 23480 KB Output is correct
13 Correct 200 ms 23808 KB Output is correct
14 Correct 223 ms 22972 KB Output is correct
15 Correct 30 ms 16080 KB Output is correct
16 Correct 187 ms 24252 KB Output is correct
17 Correct 201 ms 22208 KB Output is correct
18 Correct 139 ms 23248 KB Output is correct
19 Correct 193 ms 22472 KB Output is correct
20 Correct 159 ms 24124 KB Output is correct
21 Correct 45 ms 14552 KB Output is correct
22 Correct 253 ms 22600 KB Output is correct
23 Correct 220 ms 18920 KB Output is correct
24 Correct 247 ms 20296 KB Output is correct
25 Correct 226 ms 22496 KB Output is correct
26 Correct 246 ms 23868 KB Output is correct
27 Runtime error 32 ms 31704 KB Execution killed with signal 11
28 Halted 0 ms 0 KB -