Submission #818593

#TimeUsernameProblemLanguageResultExecution timeMemory
818593alvingogoDungeons Game (IOI21_dungeons)C++17
0 / 100
3593 ms2097152 KiB
#include "dungeons.h" #include <bits/stdc++.h> #define fs first #define sc second #define p_q priority_queue using namespace std; const int A=25; typedef long long ll; struct xe{ int to; ll cost=0; }; struct no{ vector<xe> as; no(){ as.resize(A); } }; vector<vector<no> > f; vector<int> s,p,w,l; vector<ll> g; 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; g.resize(n); for(int i=0;i<n;i++){ g[i]=s[i]; } g.push_back(1e14); g.push_back(0); sort(g.begin(),g.end()); g.erase(unique(g.begin(),g.end()),g.end()); for(int e=0;e<g.size();e++){ vector<no> v; v.resize(n+1); for(int i=0;i<n;i++){ if(g[e]>=s[i]){ v[i].as[0].to=w[i]; v[i].as[0].cost=s[i]; } else{ v[i].as[0].to=l[i]; v[i].as[0].cost=s[i]; } } for(int i=1;i<A;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; } } } f.push_back(v); } g.push_back(2e14); return; } ll simulate(int x, int z) { for(int j=0;j+1<g.size();j++){ for(int i=A-1;i>=0;i--){ if(z+f[j][x].as[i].cost<=g[j+1]){ z+=f[j][x].as[i].cost; x=f[j][x].as[i].to; if(x==n){ return z; } } } if(z>=s[x]){ z+=s[x]; x=w[x]; } else{ z+=p[x]; x=l[x]; } if(x==n){ return z; } } return z; }

Compilation message (stderr)

dungeons.cpp: In function 'void init(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
dungeons.cpp:38:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |  for(int e=0;e<g.size();e++){
      |              ~^~~~~~~~~
dungeons.cpp: In function 'll simulate(int, int)':
dungeons.cpp:70:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |  for(int j=0;j+1<g.size();j++){
      |              ~~~^~~~~~~~~
#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...