Submission #1082385

#	Time	Username	Problem	Language	Result	Execution time	Memory
1082385		HappyCapybara	Dungeons Game (IOI21_dungeons)	C++17	62 / 100	7055 ms	1453024 KiB

dungeons

#include "dungeons.h"
#include<bits/stdc++.h>
using namespace std;

#define ll long long

int st;
int n;
vector<int> s, p, w, l, ds;
vector<vector<vector<pair<int,ll>>>> v;
vector<vector<vector<ll>>> u;

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;

    for (int i=0; i<n; i++){
        int b = true;
        for (int x : ds){
            if (x == s[i]) b = false;
        }
        if (b) ds.push_back(s[i]);
    }

    if (ds.size() > 5) st = 0;
    else st = 1;

    s.push_back(0);
    p.push_back(0);
    w.push_back(n);
    l.push_back(n);

    if (st == 0){
        u.resize(n+1, vector<vector<ll>>(30));
	    for (int i=0; i<30; i++){
		    for (int j=0; j<=n; j++){
			    if (i == 0) u[j][i] = {w[j], s[j], s[j]};
			    else {
				    u[j][i].push_back(u[u[j][i-1][0]][i-1][0]);
				    u[j][i].push_back(u[j][i-1][1] + u[u[j][i-1][0]][i-1][1]);
                    u[j][i].push_back(max(u[j][i-1][2], u[u[j][i-1][0]][i-1][2]-u[j][i-1][1]));
			    }
		    }
	    }
	    return;
    }

    ds.push_back(0);
    sort(ds.begin(), ds.end());
	v.resize(ds.size(), vector<vector<pair<int,ll>>>(n+1, vector<pair<int,ll>>(30)));
    for (int k=0; k<ds.size(); k++){
	    for (int i=0; i<30; i++){
		    for (int j=0; j<=n; j++){
			    if (i == 0){
				    if (ds[k] < s[j] ) v[k][j][i] = {l[j], p[j]};
				    else v[k][j][i] = {w[j], s[j]};
			    }
			    else {
				    v[k][j][i].first = v[k][v[k][j][i-1].first][i-1].first;
				    v[k][j][i].second = v[k][j][i-1].second + v[k][v[k][j][i-1].first][i-1].second;
			    }
		    }
	    }
    }
    /*for (int k=0; k<1; k++){
        for (int i=0; i<n; i++){
            for (int j=0; j<5; j++){
                cout << v[k][i][j].first << " " << v[k][i][j].second << "\n";
            }
            cout << "\n";
        }
    }*/
	return;
}

ll simulate(int x, int z){
    if (st == 0){
        ll y = z;
        while (x != n){
		    int i = 0;
		    while (u[x][i][2] <= y){
                i++;
                if (u[x][i-1][0] == n) break;
            }
            if (i == 0){
                y += p[x];
                x = l[x];
            }
            else {
                y += u[x][i-1][1];
                x = u[x][i-1][0];
            }
	    }
	    return y;
    }


	ll y = z;
    int cur = 0;
    while (cur < ds.size()){
	    while ((cur == ds.size()-1 || y < ds[cur+1]) && x != n){
		    int i = 0;
		    while ((cur == ds.size()-1 || y+v[cur][x][i+1].second < ds[cur+1]) && v[cur][x][i].first != n) i++;
            y += v[cur][x][i].second;
		    x = v[cur][x][i].first;
	    }
        cur++;
    }
	return y;
}

Compilation message (stderr)

dungeons.cpp: In function 'void init(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
dungeons.cpp:54:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |     for (int k=0; k<ds.size(); k++){
      |                   ~^~~~~~~~~~
dungeons.cpp: In function 'long long int simulate(int, int)':
dungeons.cpp:103:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |     while (cur < ds.size()){
      |            ~~~~^~~~~~~~~~~
dungeons.cpp:104:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |      while ((cur == ds.size()-1 || y < ds[cur+1]) && x != n){
      |              ~~~~^~~~~~~~~~~~~~
dungeons.cpp:106:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |       while ((cur == ds.size()-1 || y+v[cur][x][i+1].second < ds[cur+1]) && v[cur][x][i].first != n) i++;
      |               ~~~~^~~~~~~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 26 / 26
• Subtask 3: 13 / 13
• Subtask 4: 12 / 12
• Subtask 5: 0 / 27
• Subtask 6: 0 / 11