제출 #616035

#제출 시각아이디문제언어결과실행 시간메모리
616035Clan328던전 (IOI21_dungeons)C++17
13 / 100
747 ms361144 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef vector<int> vi; typedef vector<ll> vl; typedef vector<vi> vvi; typedef vector<vl> vvl; typedef pair<int, int> pii; typedef pair<ll, ll> pll; int n; vector<pair<ll, ll>> G, W; vl dp; const int LOG = 25; vector<vvi> up; vector<vvl> sum; vi diffS; ll getDP(int i) { if (dp[i] != -1) return dp[i]; if (i == n) { dp[i] = 0; return 0; } dp[i] = W[i].first+getDP(G[i].first); return dp[i]; } pll dist(int x, int d, int j) { ll strength = 0; for (int i = LOG-1; i >= 0; i--) { if ((d>>i)&1) { strength += sum[j][x][i]; x = up[j][x][i]; } } return {x, strength}; } void init(int nx, vi s, vi p, vi w, vi l) { n = nx; G = vector<pll>(n); W = vector<pll>(n); for (int i = 0; i < n; i++) { G[i] = {w[i], l[i]}; W[i] = {s[i], p[i]}; } set<int> tmp; for (int i = 0; i < n; i++) tmp.insert(s[i]); for (auto it = tmp.begin(); it != tmp.end(); it++) { diffS.push_back(*it); } dp = vl(n+1, -1); for (int i = 0; i <= n; i++) { dp[i] = getDP(i); } up = vector<vvi>(diffS.size(), vvi(n+1, vi(LOG))); sum = vector<vvl>(diffS.size(), vvl(n+1, vl(LOG))); ll curr = 0; for (int j = 0; j < diffS.size(); j++) { up[j][n][0] = n; sum[j][n][0] = 0; for (int i = 0; i < n; i++) { if (W[i].first <= curr) { up[j][i][0] = G[i].first; sum[j][i][0] = W[i].first; } else { up[j][i][0] = G[i].second; sum[j][i][0] = W[i].second; } } for (int i = 1; i < LOG; i++) { for (int v = 0; v <= n; v++) { sum[j][v][i] = sum[j][v][i-1] + sum[j][up[j][v][i-1]][i-1]; up[j][v][i] = up[j][up[j][v][i-1]][i-1]; } } curr = diffS[j]; } } ll simulate(int x, int z) { if (z >= W[0].first) { return z + dp[x]; } ll strength = z; int res; for (int i = 0; i < diffS.size(); i++) { int lo = 0, hi = 2e7, mid; res = 2e7; while (lo <= hi) { mid = (lo+hi)/2; if (dist(x, mid, i).second+strength >= diffS[i]) { res = mid; hi = mid -1; } else lo = mid + 1; } strength += dist(x, res, i).second; } return strength+dp[dist(x, res, diffS.size()-1).first]; }

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

dungeons.cpp: In function 'void init(int, vi, vi, vi, vi)':
dungeons.cpp:70:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |  for (int j = 0; j < diffS.size(); j++) {
      |                  ~~^~~~~~~~~~~~~~
dungeons.cpp: In function 'll simulate(int, int)':
dungeons.cpp:101:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |  for (int i = 0; i < diffS.size(); i++) {
      |                  ~~^~~~~~~~~~~~~~
dungeons.cpp:116:48: warning: 'res' may be used uninitialized in this function [-Wmaybe-uninitialized]
  116 |  return strength+dp[dist(x, res, diffS.size()-1).first];
      |                                                ^
#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...