제출 #826237

#제출 시각아이디문제언어결과실행 시간메모리
826237TheSahib던전 (IOI21_dungeons)C++17
63 / 100
7093 ms587024 KiB
#include "dungeons.h" #include <bits/stdc++.h> using namespace std; #define ll long long #define pii pair<int, ll> const ll oo = 1e9 + 9; const int MAX = 50005; const int LOGMAX = 27; const int startLog = 10; int n; vector<int> S, W, P, L; struct G{ array<ll, 3> par[LOGMAX + 1][MAX]; void preCalc(){ for (int j = 1; j <= LOGMAX; j++) { for (int i = 0; i <= n; i++) { int m = par[j - 1][i][0]; par[j][i][0] = par[j - 1][m][0]; par[j][i][1] = par[j - 1][i][1] + par[j - 1][m][1]; par[j][i][2] = max(par[j - 1][i][2], par[j - 1][m][2] + par[j - 1][i][1]); } } } pii lift(ll start, ll target, int v){ if(start >= target || v == n) return {v, start}; for(int j = LOGMAX; j >= 0 && v != n && start < target; --j){ if(start + par[j][v][2] < 0){ start = start + par[j][v][1]; v = par[j][v][0]; } } if(v == n){ return {n, start}; } if(start >= S[v]){ start += S[v]; v = W[v]; } else{ start += P[v]; v = L[v]; } return {v, start}; } }; vector<ll> v; G gs[LOGMAX - startLog + 1]; void init(int N, vector<int> s, vector<int> p, vector<int> w, vector<int> l) { n = N; S = s; P = p; W = w; L = l; for(int i = startLog; i < LOGMAX; ++i){ v.push_back((1 << i)); } for (int i = 0; i < v.size(); i++) { for(int j = 0; j <= N; ++j){ if(j == N){ gs[i].par[0][j] = {N, 0, -oo * oo}; continue; } if(s[j] > v[i]){ gs[i].par[0][j] = {l[j], p[j], p[j] - s[j]}; } else{ gs[i].par[0][j] = {w[j], s[j], -oo * oo}; } } gs[i].preCalc(); } v.push_back(oo * oo); return; } ll simulate(int x, int z) { ll u = x; ll s = z; while(s < (1 << startLog) && u != n){ if(s >= S[u]){ s += S[u]; u = W[u]; } else{ s += P[u]; u = L[u]; } } for (int i = 0; i < v.size() - 1; i++) { while(u != n && s < v[i + 1]){ pii p = gs[i].lift(s, v[i + 1], u); u = p.first; s = p.second; } } return s; }

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

dungeons.cpp: In function 'void init(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
dungeons.cpp:68:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |     for (int i = 0; i < v.size(); i++)
      |                     ~~^~~~~~~~~~
dungeons.cpp: In function 'long long int simulate(int, int)':
dungeons.cpp:101:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |  for (int i = 0; i < v.size() - 1; i++)
      |                  ~~^~~~~~~~~~~~~~
#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...