제출 #1062767

#제출 시각아이디문제언어결과실행 시간메모리
1062767TheQuantiX던전 (IOI21_dungeons)C++17
50 / 100
7066 ms310352 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; ll n, m, q, k, x, y, a, b, c; vector<int> s, p, w, l; bool testcase3, testcase2; vector<ll> up[30]; vector<ll> upmx[30]; vector<ll> upm[30]; vector<ll> wins; 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; testcase2 = 1; set<ll> st; for (int i = 0; i < n; i++) { if (s[i] != p[i]) { testcase2 = 0; } st.insert(s[i]); } if (testcase2) { for (int i = 0; i < 30; i++) { up[i].resize(n + 1); upmx[i].resize(n + 1); upm[i].resize(n + 1); if (i == 0) { for (int j = 0; j < n; j++) { upm[i][j] = w[j]; up[i][j] = s[j]; upmx[i][j] = s[j] * 2 - up[i][j]; } upm[i][n] = n; upmx[i][n] = 0; up[i][n] = 0; } else { for (int j = 0; j < n + 1; j++) { upm[i][j] = upm[i - 1][upm[i - 1][j]]; up[i][j] = up[i - 1][j] + up[i - 1][upm[i - 1][j]]; upmx[i][j] = max(upmx[i - 1][j], upmx[i - 1][upm[i - 1][j]] - up[i - 1][j]); } } } } else if (st.size() == 1) { testcase3 = 1; for (int i = 0; i < 30; i++) { up[i].resize(n + 1); upm[i].resize(n + 1); if (i == 0) { for (int j = 0; j < n; j++) { upm[i][j] = l[j]; up[i][j] = p[j]; } upm[i][n] = n; up[i][n] = 0; } else { for (int j = 0; j < n + 1; j++) { upm[i][j] = upm[i - 1][upm[i - 1][j]]; up[i][j] = up[i - 1][j] + up[i - 1][upm[i - 1][j]]; } } } // cout << "DEBUG" << endl; wins.resize(n + 1); for (int i = n - 1; i >= 0; i--) { // cout << i << ' ' << s[i] << endl; wins[i] = s[i] + wins[w[i]]; } } } long long simulate2(int x, ll z); long long simulate3(int x, ll z); long long simulate(int x, int z) { if (testcase2) { return simulate2(x, z); } if (testcase3) { return simulate3(x, z); } while (x < n) { if (z >= s[x]) { z += s[x]; x = w[x]; } else { z += p[x]; x = l[x]; } // cout << x << ' ' << z << '\n'; } return z; } long long simulate2(int x, ll z) { while (x < n) { for (int i = 29; i >= 0; i--) { // cout << i << ' ' << up[i][x] << '\n'; if (upmx[i][x] <= z) { z += up[i][x]; x = upm[i][x]; } } if (x != n) { z += p[x]; x = l[x]; } } return z; } long long simulate3(int x, ll z) { for (int i = 29; i >= 0; i--) { // cout << i << ' ' << up[i][x] << '\n'; if (z + up[i][x] < s[0] && upm[i][x] != n) { // cout << z + up[i][x] << '\n'; z += up[i][x]; x = upm[i][x]; // cout << x << ' ' << z << '\n'; } } if (z < s[0]) { z += p[x]; x = l[x]; } // cout << x << ' ' << z << '\n'; z += wins[x]; // cout << n << ' ' << z << '\n'; return z; }
#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...