제출 #439950

#제출 시각아이디문제언어결과실행 시간메모리
439950dacin21던전 (IOI21_dungeons)C++17
37 / 100
7075 ms137284 KiB
#pragma GCC optimize("O3") #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx") // codeforces #include "dungeons.h" #include <bits/stdc++.h> using namespace std; using ll = int64_t; const int BLOCK = 10000; const int MAX_SKILL = 1.01e7; const int U = 16; const int inf = 1e9; int n; struct Link{ int to; int gain; }; struct Node{ Link win, loss; int thresh; }; struct Jump{ int to; int max_valid; ll gain; }; vector<ll> win_gain; vector<Node> g; vector<vector<Jump> > jumps; void init(int n_, vector<int> s, vector<int> p, vector<int> w, vector<int> l){ n = n_; g.assign(n+1, Node{}); for(int i=0; i<n; ++i){ g[i] = Node{Link{w[i], s[i]}, Link{l[i], p[i]}, s[i]}; } g[n] = Node{Link{n, 0}, Link{n, 0}, 0}; // compute win once we hit 1e7 win_gain.assign(n+1, 0); for(int i=n-1; i>=0; --i){ win_gain[i] = win_gain[g[i].win.to] + g[i].win.gain; } // assume we take BLOCK steps // then build jump table jumps.resize(U+1, vector<Jump>(n+1)); for(int i=0; i<=n; ++i){ if(g[i].thresh <= BLOCK){ jumps[0][i] = Jump{g[i].win.to, inf, g[i].win.gain}; } else { jumps[0][i] = Jump{g[i].loss.to, g[i].thresh-1, g[i].loss.gain}; } } jumps[0][n].max_valid = 0; for(int i=1; i<=U; ++i){ for(int j=0; j<=n; ++j){ auto &e = jumps[i-1][j]; const int k = e.to; auto const&f = jumps[i-1][k]; jumps[i][j] = Jump{f.to, max<ll>(-1, min<ll>(e.max_valid, f.max_valid-e.gain)), e.gain+f.gain}; } } } long long simulate(int x, int z) { int u = x; ll s = z; auto do_single_step = [&](){ if(s >= g[u].thresh){ s += g[u].win.gain; u = g[u].win.to; } else { s += g[u].loss.gain; u = g[u].loss.to; } }; for(int it=0; it<BLOCK; ++it){ do_single_step(); } assert(u == n || s >= BLOCK); while(u != n && s < MAX_SKILL){ int i = 0; while(i >= 0){ auto &e = jumps[i][u]; if(s < e.max_valid){ s += e.gain; u = e.to; i = min(i+1, U); } else --i; } do_single_step(); } s += win_gain[u]; return s; }

컴파일 시 표준 에러 (stderr) 메시지

dungeons.cpp: In function 'void init(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
dungeons.cpp:63:45: warning: narrowing conversion of '(long int)std::max<long int>(-1, (* & std::min<long int>(((long int)e.Jump::max_valid), (((ll)((int)f.Jump::max_valid)) - e.Jump::gain))))' from 'long int' to 'int' [-Wnarrowing]
   63 |             jumps[i][j] = Jump{f.to, max<ll>(-1, min<ll>(e.max_valid, f.max_valid-e.gain)), e.gain+f.gain};
      |                                      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...