Submission #828960

#TimeUsernameProblemLanguageResultExecution timeMemory
828960LiudasDungeons Game (IOI21_dungeons)C++17
24 / 100
7078 ms317388 KiB
#include "dungeons.h" #include <vector> #include <cassert> #include <cstdio> #include <iostream> #include <fstream> #include <numeric> #include <algorithm> using namespace std; struct node{ long long ws, ls, w, l, dep; vector<long long> child; vector<long long> par; vector<long long> cv; }; int cas; vector<node> tree; void dfs(int head, long long c){ c += tree[head].ws; tree[head].dep = c; for(int i : tree[head].par){ dfs(i, c); } } void init(int n, vector<int> s, vector<int> p, vector<int> w, vector<int> l){ if(count(s.begin(), s.end(), s[0]) == n){ cas = 1; } else{ cas = 0; } tree.resize(n+1); for(int i = 0; i < n; i ++){ tree[i].ws = s[i]; tree[i].ls = p[i]; tree[i].w = w[i]; tree[i].l = l[i]; tree[w[i]].par.push_back(i); tree[i].child.push_back(l[i]); tree[i].cv.push_back(p[i]); } tree[n].child.push_back(n); tree[n].cv.push_back(0); tree[n].ws = 0; dfs(n, 0); for(int i = 0; i < 30; i ++){ for(int j = 0; j <= n; j ++){ tree[j].child.push_back(tree[tree[j].child[i]].child[i]); tree[j].cv.push_back(tree[tree[j].child[i]].cv[i] + tree[j].cv[i]); } } } long long simulate(int x, int z){ long long ans = z; if(cas){ while(x + 1 != tree.size()){ if(ans >= tree[x].ws){ ans += tree[x].dep; x = tree.size()-1; } else{ int p = 0; while(tree[x].cv[p + 1] + ans < tree[tree[x].child[p+1]].ws && p < 25){ p++; } ans += tree[x].cv[p]; x = tree[x].child[p]; } } } else{ while(x + 1 != tree.size()){ if(ans >= tree[x].ws){ ans += tree[x].ws; x = tree[x].w; } else{ ans += tree[x].ls; x = tree[x].l; } } } return ans; }

Compilation message (stderr)

dungeons.cpp: In function 'long long int simulate(int, int)':
dungeons.cpp:56:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |         while(x + 1 != tree.size()){
      |               ~~~~~~^~~~~~~~~~~~~~
dungeons.cpp:72:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |         while(x + 1 != tree.size()){
      |               ~~~~~~^~~~~~~~~~~~~~
#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...