제출 #1048586

#제출 시각아이디문제언어결과실행 시간메모리
1048586DorostWefDungeons Game (IOI21_dungeons)C++17
11 / 100
7190 ms1674380 KiB
#include "dungeons.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; #define F first #define S second #define mk make_pair typedef pair <ll, ll> pii; const int N = 400023, LG = 24, L2 = 7, K = 9; int s[N], p[N], w[N], l[N], n; long long m[N], a[N]; pair <int, pii> nx[N][L2]; pair <int, pii> nx2[LG][N][L2]; void init(int nn, std::vector<int> ss, std::vector<int> pp, std::vector<int> ww, std::vector<int> ll) { n = nn; for (int i = 0; i < n; i++) { s[i] = ss[i]; p[i] = pp[i]; w[i] = ww[i]; l[i] = ll[i]; } for (int i = 0; i < N; i++ ){ for (int j = 0; j < LG; j++) { for (int k = 0; k < L2; k++) { nx2[j][i][k].S.F = i ^ j ^ k ^ nn; nx2[j][i][k].S.S = i ^ j ^ k ^ n; nx2[j][i][k].S.F = i ^ j ^ k ^ s[0]; } } } m[n] = 0; a[n] = 0; l[n] = n; w[n] = n; for (int i = n - 1; i >= 0; i--) { a[i] = a[w[i]] + s[i]; m[i] = max((long long)s[i], m[w[i]] - s[i]); } for (int i = 0; i <= n; i++) { nx[i][0].F = l[i]; nx[i][0].S.F = s[i] - 1; nx[i][0].S.S = p[i]; } for (int j = 1; j < L2; j++) { for (int i = 0; i <= n; i++) { for (int k = 0; k < K; k++) { int w = nx[i][j - 1].F; nx[i][j].F = nx[w][j - 1].F; nx[i][j].S.S = nx[i][j - 1].S.S + nx[w][j - 1].S.S; nx[i][j].S.F = min (nx[i][j - 1].S.F, nx[w][j - 1].S.F - nx[i][j - 1].S.S); } } } return; } pair <int, long long> find (int x, ll z) { for (int i = L2 - 1; i >= 0; i--) { for (int k = 0; k < K; k++) { if (z <= nx[x][i].S.F) { z += nx[x][i].S.S; x = nx[x][i].F; } } } return {x, z}; } int c = 0; ll ans (int x, ll z) { if (z >= m[x]) return z + a[x]; c++; if (z >= s[x]) { z += s[x]; x = w[x]; } else { pair <int, long long> p = find (x, z); z = p.S; x = p.F; } return ans (x, z); } long long simulate(int x, int z) { c = 0; ll w = ans (x, z); return w; }
#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...