Submission #896286

#TimeUsernameProblemLanguageResultExecution timeMemory
896286Ghulam_JunaidDungeons Game (IOI21_dungeons)C++17
0 / 100
7058 ms15940 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; const ll N = 4e5 + 10; ll n; vector<ll> s, p, w, l; vector<ll> win; ll g[N]; bool subtask2, vis[N]; set<pair<ll, ll>> st; void dfs(ll v){ vis[v] = 1; st.insert({s[v], v}); if (!vis[w[v]]) dfs(w[v]); auto ub = st.upper_bound({2 * s[v], 0}); if (ub == st.end()) g[v] = -1; else g[v] = (*ub).second; st.erase({s[v], v}); } void init(int inp_n, vector<int> S, vector<int> P, vector<int> W, vector<int> L){ n = inp_n; for (ll x : S) s.push_back(x); for (ll x : P) p.push_back(x); for (ll x : W) w.push_back(x); for (ll x : L) l.push_back(x); memset(g, -1, sizeof g); win.resize(n + 1, 0); for (ll i = n - 1; i >= 0; i--){ if (w[i] == n) win[i] = s[i]; else win[i] = s[i] + win[w[i]]; } for (ll i = 0; i < n; i ++){ if (!vis[i]) dfs(i); } subtask2 = 1; for (ll i=0; i<n; i++) subtask2 &= (s[i] == p[i]); } ll simulate(int x, int z){ ll cur_node = x; ll cur_strength = z; while (cur_node != n){ if (s[cur_node] > cur_strength){ cur_strength += p[cur_node]; cur_node = l[cur_node]; } else{ ll u = g[cur_node]; if (u == -1){ cur_strength += win[cur_node]; break; } cur_strength += win[cur_node] - win[u]; cur_node = u; } } return cur_strength; }
#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...