Submission #1211755

#TimeUsernameProblemLanguageResultExecution timeMemory
1211755ksu2009enDungeons Game (IOI21_dungeons)C++20
26 / 100
433 ms254852 KiB
#include <iostream> #include <vector> #include <string> #include <math.h> #include <cmath> #include <iomanip> #include <cstdio> #include <algorithm> #include <numeric> #include <map> #include <set> #include <queue> #include <stack> #include <deque> #include <bitset> #include <cstring> #include <unordered_map> using namespace std; typedef long long ll; #include "dungeons.h" bool group3 = true, group2 = true; ll t2[(ll)(4e5 + 7)][20][3]; vector<int> d3[(ll)(4e5 + 7)]; vector<ll> s, p, w, l; ll n; void build_t2(ll v, ll par){ t2[v][0][0] = par; t2[v][0][1] = t2[v][0][2] = s[v]; for(int i = 1; i < 20; i++){ t2[v][i][0] = t2[t2[v][i - 1][0]][i - 1][0]; t2[v][i][1] = t2[v][i - 1][1] + t2[t2[v][i - 1][0]][i - 1][1]; t2[v][i][2] = max(t2[v][i - 1][2], t2[t2[v][i - 1][0]][i - 1][2]); } for(auto i: d3[v]) if(i != par) build_t2(i, v); } void init(int n0, std::vector<int> s0, std::vector<int> p0, std::vector<int> w0, std::vector<int> l0){ n = n0; s.resize(n + 1); p.resize(n + 1); w.resize(n + 1); l.resize(n + 1); for(ll i = 1; i <= n; i++){ s[i] = s0[i - 1], p[i] = p0[i - 1], w[i] = w0[i - 1], l[i] = l0[i - 1]; w[i]++, l[i]++; } for(int i = 1; i <= n; i++){ if(s[i] != s[1]) group3 = false; if(s[i] != p[i]) group2 = false; } if(group2){ for(int i = 1; i <= n; i++) d3[w[i]].push_back(i); build_t2(n + 1, 0); } } ll cor(ll x, ll z){ while(x != n + 1){ if(z >= s[x]){ z += s[x]; x = w[x]; } else{ z += p[x]; x = l[x]; } } return z; } long long simulate(int x, int z){ x++; if(!group3 && !group2) return cor(x, z); if(group2){ while(x != n + 1){ for(int i = 19; i >= 0; i--){ if(t2[x][i][0] != 0 && z >= t2[x][i][2]){ z += t2[x][i][1]; x = t2[x][i][0]; } } if(x != n + 1 && z < s[x]){ z += s[x]; x = l[x]; } } return z; } return 0; } /* 4 1 3 5 2 1 3 5 2 1 1 3 3 4 0 3 2 1 0 4 2 5 */
#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...