제출 #485868

#제출 시각아이디문제언어결과실행 시간메모리
485868rumen_m던전 (IOI21_dungeons)C++17
63 / 100
5039 ms1097088 KiB
#include "dungeons.h" #include <vector> #include <bits/stdc++.h> using namespace std; const long long maxn = 50005; const long long logn = 24; const long long INF = 1e18; long long nextt[maxn][logn][logn],add[maxn][logn][logn],treshold[maxn][logn][logn]; long long sums[maxn]; bool vis[maxn]; long long n; vector <long long> s,p,w,l; long long dfs(long long v) { if(v==n)return 0; if(vis[v])return sums[v]; sums[v] = s[v] + dfs(w[v]); vis[v] = 1; return sums[v]; } void init(int _n, std::vector<int> _s, std::vector<int> _p, std::vector<int> _w, std::vector<int> _l) { long long i,j; n = _n; s.resize(_s.size()); for(i=0;i<_s.size();i++) s[i] = _s[i]; p.resize(_p.size()); for(i=0;i<_p.size();i++) p[i] = _p[i]; w.resize(_w.size()); for(i=0;i<_w.size();i++) w[i] = _w[i]; l.resize(_l.size()); for(i=0;i<_l.size();i++) l[i] = _l[i]; for(int t = 0; t<logn; t++) { long long from = (1<<t); long long to = (1<<(t+1)); for(i=0;i<n;i++) { if(s[i]>to){ nextt[i][0][t] = l[i]; add[i][0][t] = p[i]; treshold[i][0][t] = INF; } else if(s[i]<=from) { nextt[i][0][t] = w[i]; add[i][0][t] = s[i]; treshold[i][0][t] = INF; } else { nextt[i][0][t] = l[i]; add[i][0][t] = p[i]; treshold[i][0][t] = s[i]; } } nextt[n][0][t] = n; treshold[n][0][t] = INF;//cout<<t<<endl; for(i=1;i<logn;i++) { for(j=0;j<=n;j++) { nextt[j][i][t] = nextt[nextt[j][i-1][t]][i-1][t]; add[j][i][t] = add[j][i-1][t]+add[nextt[j][i-1][t]][i-1][t]; treshold[j][i][t] = max((long long)0,min(treshold[j][i-1][t],treshold[nextt[j][i-1][t]][i-1][t]-add[j][i-1][t])); // cout<<j<<" "<<i<<" "<<t<<" -> "<<nextt[j][i][t]<<" "<<add[j][i][t]<<" "<<treshold[j][i][t]<<endl; } } } for(i=0;i<=n;i++) { dfs(i); } } long long simulate(int _x, int _z) { long long x = _x; long long z = _z; if(x==n)return z;// cout<<"&&"<<n<<endl; int i; for(int t = 0; t < logn; t++) { // cout<<x<<" "<<z<<endl; long long to = (1<<(t+1)); for(i = logn-1; i>=0;i--) { // cout<<i<<" curr: "<<x<<" "<<z<<endl; if(x==n)return z; if(treshold[x][i][t]>z&&add[x][i][t]+z < to) { z += add[x][i][t]; x = nextt[x][i][t]; } } // cout<<"predi last: "<<x<<" "<<z<<endl; if(x==n)return z; if(z<to) { if(s[x]>z) { z+=p[x]; x = l[x]; } else { z+=s[x]; x = w[x]; } } // cout<<"final: "<<x<<" "<<z<<endl; } z += sums[x]; return z; }

컴파일 시 표준 에러 (stderr) 메시지

dungeons.cpp: In function 'void init(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
dungeons.cpp:26:11: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |  for(i=0;i<_s.size();i++)
      |          ~^~~~~~~~~~
dungeons.cpp:29:11: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |  for(i=0;i<_p.size();i++)
      |          ~^~~~~~~~~~
dungeons.cpp:32:11: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |  for(i=0;i<_w.size();i++)
      |          ~^~~~~~~~~~
dungeons.cpp:35:11: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |  for(i=0;i<_l.size();i++)
      |          ~^~~~~~~~~~
#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...