oj.uz

답안 #868171

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
868171 2023-10-30T16:12:50 Z nnhzzz Soccer (JOI17_soccer) C++14
35 / 100
 395 ms 52700 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){
        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)==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));
            }
            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:123:21: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  123 |         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 53 ms 8404 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 256 ms 33108 KB Output is correct
4 Correct 259 ms 32704 KB Output is correct
5 Correct 36 ms 9308 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 287 ms 33212 KB Output is correct
2 Correct 295 ms 33404 KB Output is correct
3 Correct 202 ms 29188 KB Output is correct
4 Correct 192 ms 33972 KB Output is correct
5 Correct 202 ms 28292 KB Output is correct
6 Correct 213 ms 33224 KB Output is correct
7 Correct 333 ms 33904 KB Output is correct
8 Correct 264 ms 34540 KB Output is correct
9 Correct 320 ms 33080 KB Output is correct
10 Correct 32 ms 6608 KB Output is correct
11 Correct 315 ms 33028 KB Output is correct
12 Correct 303 ms 33208 KB Output is correct
13 Correct 157 ms 28108 KB Output is correct
14 Correct 339 ms 34784 KB Output is correct
15 Correct 224 ms 28080 KB Output is correct

Subtask #3
0 / 65.0

# 결과 실행 시간 메모리 Grader output
1 Correct 53 ms 8404 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 256 ms 33108 KB Output is correct
4 Correct 259 ms 32704 KB Output is correct
5 Correct 36 ms 9308 KB Output is correct
6 Correct 287 ms 33212 KB Output is correct
7 Correct 295 ms 33404 KB Output is correct
8 Correct 202 ms 29188 KB Output is correct
9 Correct 192 ms 33972 KB Output is correct
10 Correct 202 ms 28292 KB Output is correct
11 Correct 213 ms 33224 KB Output is correct
12 Correct 333 ms 33904 KB Output is correct
13 Correct 264 ms 34540 KB Output is correct
14 Correct 320 ms 33080 KB Output is correct
15 Correct 32 ms 6608 KB Output is correct
16 Correct 315 ms 33028 KB Output is correct
17 Correct 303 ms 33208 KB Output is correct
18 Correct 157 ms 28108 KB Output is correct
19 Correct 339 ms 34784 KB Output is correct
20 Correct 224 ms 28080 KB Output is correct
21 Correct 43 ms 9748 KB Output is correct
22 Correct 332 ms 34408 KB Output is correct
23 Correct 307 ms 27648 KB Output is correct
24 Correct 395 ms 30144 KB Output is correct
25 Correct 299 ms 33968 KB Output is correct
26 Correct 301 ms 33204 KB Output is correct
27 Runtime error 49 ms 52700 KB Execution killed with signal 11
28 Halted 0 ms 0 KB -