Submission #868170

#TimeUsernameProblemLanguageResultExecution timeMemory
868170nnhzzzSoccer (JOI17_soccer)C++14
35 / 100
281 ms28876 KiB
// 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 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)==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 (stderr)

soccer.cpp: In function 'void solve()':
soccer.cpp:121:21: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  121 |         const auto &[x,y] = q.front(); q.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);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...