Submission #818523

#TimeUsernameProblemLanguageResultExecution timeMemory
818523alvingogoDungeons Game (IOI21_dungeons)C++17
26 / 100
452 ms225980 KiB
#include "dungeons.h" #include <bits/stdc++.h> #define fs first #define sc second #define p_q priority_queue using namespace std; typedef long long ll; struct xe{ int to; ll cost=0; ll mx=0; }; struct no{ vector<xe> as; no(){ as.resize(20); } }; vector<no> v; vector<int> s,p,w,l; int n; 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; v.resize(n+1); for(int i=0;i<n;i++){ v[i].as[0].to=w[i]; v[i].as[0].cost=s[i]; v[i].as[0].mx=s[i]; } for(int i=1;i<20;i++){ for(int j=0;j<n;j++){ auto a=v[j].as[i-1],b=v[v[j].as[i-1].to].as[i-1]; if(a.to==n){ v[j].as[i]=a; } else{ v[j].as[i].to=b.to; v[j].as[i].cost=a.cost+b.cost; v[j].as[i].mx=max(a.mx,b.mx-a.cost); } } } return; } ll simulate(int x, int z) { while(x!=n){ for(int i=19;i>=0;i--){ if(v[x].as[i].mx>z){ continue; } else{ z+=v[x].as[i].cost; x=v[x].as[i].to; if(x==n){ return z; } } } z+=s[x]; x=l[x]; } 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...